最大和子序列问题

// hhh.cpp : 定义控制台应用程序的入口点。//

#include "stdafx.h"#include <iostream>

using namespace std;

int MaxSub_Sum(const int A[ ], int N,int &seqStart, int&seqEnd){ int thisSum ,MaxSum ,i , j; thisSum=0; MaxSum=0; i=0;   /*   从左至右相加，若如结果是不断增加的，那么thisSum和MaxSum一起增加   若遇到负数，那么也加到ThisSum上去。此时ThisSum<MaxSum,那么不加到MaxSum上去。   看ThisSum是不是会回升，若一直不回升，不是或者波浪型下降。   若降到0时，前面上升阶段和下降阶段可以抛弃了，开始一个新的阶段，此时thisSum=0，   但是MaxSum仍然保留的着前上升阶段的最大值。   然后，ThisSum开始将从后面新的子段开始分析，若有比当前的MaxSum大的子段，然后替换。（将彻底抛弃前段上升阶段的MaxSum）   时间复杂度为O（N)

   */ for(j=0;j<N;j++) {  thisSum+=A[j];  if(thisSum>MaxSum)  {   MaxSum=thisSum;   seqStart=i;   seqEnd=j;  }  else if(thisSum<0)  {    i=j+1;    thisSum=0;   }  }

return MaxSum;}

int _tmain(int argc, _TCHAR* argv[]){ int a[]={1 ,2, -1, 1, 3 ,2 ,-2, 3, -1, 5, -7, 3 ,2, -2 ,-1}; int size=sizeof(a)/sizeof(int); int start=0; int end=0; int MaxSum=MaxSub_Sum(a,size,start,end); cout<<MaxSum<<"    "<<start<<"    "<<end<<endl;

 return 0;}