数组结对开发

浏览数：19 / 时间：2015年06月08日

题目：返回一个整数数组中最大子数组

要求：输入一个整形数组，数组里有整数也有负数；

数组中连续的一个或多个整数组成一个整数组每个子数组都有一个和；

求所有子数组的和的最大值，要求时间复杂度为O（n）。

思路：设数组为a[5],则所有子数组的和可以为

(1) a[0]+a[1]+a[2]+a[3]+a[4](2)a[1]+a[2]+[3]+a[4]

a[0]+a[1]+a[2]+a[3] a[1]+a[2]+[3]

a[0]+a[1]+a[2] a[1]+a[2]

a[0]+a[1] a[1]

a[0]

……….以此类推五个分组，每个分组都有它的最大值，存放在数组max[5]中，最后得出数组max[5]的最大值即为题目所求。

具体实现代码：

 1 #include<iostream.h>
 2 #include<conio.h>
 3 int main()
 4 {
 5     int arr[5];
 6     int i,j;
 7     int max[5];
 8     int jixu;
 9     cout<<"input array:"<<endl;
10     for(i=0;i<5;i++)
11     {
12         cin>>arr[i];
13     }
14     for(i=0;i<5;i++)
15     {
16         max[i]=arr[i];
17     }
18     for(j=0;j<4;j++)
19     {
20         for(i=j+1;i<5;i++)
21         {
22             arr[j]=arr[j]+arr[i];
23             if(max[j]<arr[j])
24             {
25             max[j]=arr[j];
26             }
27         }
28     }
29     for(i=0;i<5;i++)
30     {
31         if(max[0]<max[i])
32             max[0]=max[i];
33     }
34     cout<<"ADDmax="<<max[0]<<endl;
35     cout<<"是否要继续？jixu(0,退出  1，继续)"<<endl;
36     cin>>jixu;
37     if(jixu==1)
38     {
39         cout<<endl;
40         main();
41     }
42     else
43     {
44         return 0;
45     }
46     getch();
47     return 0;
48 
49 }