最大子段和

问题

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

思路

从第一个元素开始，计算1－2的和、1－3的和、直到1－n的和，sum来记录最大的和，在循环过程中如果有和比sum大，把当前最大和替换掉，记录besti和bestj；然后计算2－3的和、2－4的和、直到2－n的和。需要2次for循环，时间复杂度O(n^2).

代码

#include <iostream>
using namespace std;
//求a中的最大子段和
int maxSum(int a[],int n){
   int i,j,sum=0,besti,bestj;
   for(i=0;i<4;i++){
      int newsum=0;
      for ( j= i; j <n; ++j)
      {
          newsum+=a[j];
          if(newsum>sum){
             sum=newsum;
             besti=i;
             bestj=j;
          }
      }
   }
   cout<<"开始位置："<<a[besti]<<endl;
   cout<<"开始位置："<<a[bestj]<<endl;

   return 0;
}
int main(){
     int a[6]={-2,11,-4,13,-5,-2};
     maxSum(a,6);

     int b[10]={1,-5,6,-2,11,-7,23,-13,15,-3};
     maxSum(b,10);
}

输出

开始位置：11
开始位置：13
开始位置：6
开始位置：15

时间复杂度

O(n^2)