最大子列和问题，一共有四种方法来解决。
1.方法及复杂度：
方法复杂度暴力算法O(N^3)轻度暴力算法O(N^2)分而治之算法O(NlogN)在线处理O(N)2.
3.“在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。
4.修改一下第二种方法可以用来解决PAT 1007 这个题当时做的时候还是考虑的不周全，忽略了负数和0交替的情况
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> using namespace std; /*最简单的一种方法，在线处理方法，时间复杂度为O(N)*/ int MaxArraySum1(int k ,int a[]){ int ThisSum,MaxSum = 0; int start,end; for(int i =0; i < k;i++){ ThisSum += a[i]; if(ThisSum > MaxSum)//如果当前和大于目前最大值，取代 MaxSum = ThisSum; if(ThisSum < 0)//如果当前值小于0，那么他一定不会让后面加上的数更大，所以舍弃这部分数 ThisSum = 0; } return MaxSum; } int Max3( int A, int B, int C ) { /* 返回3个整数中的最大值 */ return A > B ? A > C ? A : C : B > C ? B : C; } /*分而治之算法，时间复杂度为O(NlogN)*/ int DivideAndConquer(int List[],int left,int right){ int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */ int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/ int LeftBorderSum, RightBorderSum; int center, i; if( left == right ) { /* 递归的终止条件，子列只有1个数字 */ if( List[left] > 0 ) return List[left]; else return 0; } center = (left+right)/2; /* 递归求得两边子列的最大和 */ MaxLeftSum = DivideAndConquer( List, left, center ); MaxRightSum = DivideAndConquer( List, center+1, right ); /* 下面求跨分界线的最大子列和 */ MaxLeftBorderSum = 0; LeftBorderSum = 0; for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */ LeftBorderSum += List[i]; if( LeftBorderSum > MaxLeftBorderSum ) MaxLeftBorderSum = LeftBorderSum; } /* 左边扫描结束 */ MaxRightBorderSum = 0; RightBorderSum = 0; for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */ RightBorderSum += List[i]; if( RightBorderSum > MaxRightBorderSum ) MaxRightBorderSum = RightBorderSum; } /* 右边扫描结束 */ /* 下面返回"治"的结果 */ return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum ); } int MaxArraySum2(int k ,int a[]){ return DivideAndConquer( a, 0, k-1 ); } /*如果要求找出起始位置和终止位置，用O(n^2)的方法比较好*/ int* MaxArraySum3(int k,int a[]){ int CurrentSum,MaxSum=0; int left,right; int count = 0; for(int i = 0;i < k;i++){ CurrentSum = 0; if(a[i] < 0) count++; for(int j = i;j < k;j++){ CurrentSum += a[j]; if(CurrentSum > MaxSum){//如果当前和大于最大值，取代 MaxSum = CurrentSum; left = a[i]; right = a[j]; } if(CurrentSum == 0&& MaxSum == 0){//注意这种情况可以处理负数和0交替的情况，eg:5 -1 0 -1 0 -1 MaxSum = CurrentSum; left = a[i]; right = a[j]; } } } int* result = new int[3]; if(count == k){//如果输入的数都是负数 result[0] = 0; result[1] = a[0]; result[2] = a[k-1]; } else{ result[0] = MaxSum; result[1] = left; result[2] = right; } return result;//返回数组要返回一个指针 } int main(int argc,char *argv[]){ int k; scanf("%d",&k); int a[100000]; for(int i = 0;i < k;i++){ cin >> a[i]; } int result; result = MaxArraySum2(k,a); printf("%d" , result); /* int* b; b = MaxArraySum3(k,a); for(int i = 0; i < 2;i++) printf("%d " , b[i]); printf("%d" , b[2]); //delete[] b; return 0; */ }