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

求所有子数组的和的最大值。要求时间复杂度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 
     
       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
      
       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<
       
        <<" ";49     }50     cout<
       
      
     

运行结果:

 

 

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

1 #include 
     
       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
      
       MaxSum)21             MaxSum=f[i];22     }23     for(int k=0;k
      
     

运行截图: