面试题31.连续子数组的最大和

题目:输入一个整型数组，数组里有正数也有负数。数组中一个或者连续多个整数组成一个子数组。

求所有子数组的和的最大值。要求时间复杂度O(n)

本题可以把所有子数组全部找出来再求其和的最大值便可以得出，但是这样会导致算法的时间复杂度

为0(n^2)，所以有两种方法来解决这个问题。

方法1.数组扫描

我们扫描一遍数组并且累加数组元素的和，当遇到累加和为负数的时候，我们从数组中

下一个元素开始重新累加。直到遍历完成。

方法2.动态规划的方法

有这样一个公式

　 { pdata[i] if f(i-1)<=0

f(i){

{f(x-i)+pdata[i] if f(i-1)>0

怎么理解呢，f(i)是一个数组，其代表数组中第1-i个子数组的最大和，当f(i-1)为负的时候，此时加上一个pdata[i]会更小

所以f(i)=pdata[i]

当f(i-1)为正的时候，此时加上一个pdata[i]会更大，所以f(i)=f(i-1)+pdata[i];

下面我们分别实现两种方法:

第一种扫描法(如果只想找最大的则不必找出最大子数组到底是哪些元素，复杂度0(n))

 1 #include <iostream>
 2 using namespace std;
 3 
 4 
 5 int FindSerialMaxSum(int* pData,int nLength)
 6 {
 7     int CurrSum=0;
 8     int MaxSum=0;
 9 
10     if(pData==NULL||nLength==0)
11         return 0;
12     int *ChildArray=new int[nLength];
13     for(int k=0;k<nLength;k++)
14         ChildArray[k]=0;
15 
16     int index=0;
17 
18     for(int i=0;i<nLength;i++)
19     {
20         if(CurrSum<=0)
21         {
22             CurrSum=pData[i];
23             for(int j=0;j<nLength;j++)
24                 ChildArray[j]=0;
25             index=0;
26             ChildArray[index]=pData[i];
27         }
28         else
29         {
30             CurrSum+=pData[i];
31             index++;
32             ChildArray[index]=pData[i];
33         }
34 
35         if(CurrSum>MaxSum)
36             MaxSum=CurrSum;
37     }
38 
39     int Temp=0;
40     cout<<"The Child Array is : ";
41     for(int l=0;pData[l]!=0;l++)
42     {
43         if(Temp==MaxSum)
44         {
45             break;
46         }
47         Temp+=ChildArray[l];
48         cout<<ChildArray[l]<<" ";
49     }
50     cout<<endl;
51 
52     return MaxSum;
53 }
54 
55 int main(int argc ,char* argv[])
56 {
57     int pdata[]={1,-2,3,10,-4,7,2,-5};
58     int nLength=8;
59     int SerivalSum=FindSerialMaxSum(pdata,nLength);
60     if(SerivalSum!=0)
61         cout<<"The Serial Max Sum = "<<SerivalSum<<endl;
62     else
63         cout<<"Input error!"<<endl;
64     system("pause");
65     return 0;
66 }

运行结果:

2.动态规划的方法(f(i)为存储0-i子数组的最大和)

 1 #include <iostream>
 2 using namespace std;
 3 
 4 
 5 int FindSerialMaxSum(int* pData,int nLength,int* f)
 6 {
 7     f[0]=pData[0];
 8     int MaxSum=0;
 9     for(int i=1;i<nLength;i++)
10     {
11         if(f[i-1]<=0)
12         {
13             f[i]=pData[i];
14         }
15         else
16         {
17             f[i]=f[i-1]+pData[i];
18         }
19 
20         if(f[i]>MaxSum)
21             MaxSum=f[i];
22     }
23     for(int k=0;k<nLength;k++)
24     {
25         cout<<f[k]<<" ";
26     }
27     cout<<endl;
28     return MaxSum;
29 }
30 
31 int main(int argc ,char* argv[])
32 {
33     int pdata[]={1,-2,3,10,-4,7,2,-5};
34     int nLength=8;
35     int *f=new int[nLength];
36     int SerivalSum=FindSerialMaxSum(pdata,nLength,f);
37     if(SerivalSum!=0)
38         cout<<"The Serial Max Sum = "<<SerivalSum<<endl;
39     else
40         cout<<"Input error!"<<endl;
41     delete[] f;
42     system("pause");
43     return 0;
44 }

运行截图: