求子数组和的最大值及其时间复杂度分析
典型的输入能帮助我们测试算法的逻辑。 在写具体算法前列出各种可能输入，可以帮助明确题目的要求。
最直接的方法： 记 Sum[i, …, j] 为 数组A中第i个元素到第j个元素的和(其中 0 ≤ i ≤ j < n 0leq ileq j< n 0≤i≤j<n)，遍历所有可能的Sum[i, …, j] ，那么时间复杂度为 O ( N 3 ) O(N^3) O(N3)：
int MaxSum(int* A, int n){
int maximum=-INF;
int sum;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
for(int k=i;k<=j;k++){
sum+=A[k];
}
if(sum>maximum)
maximum=sum;
}
}
return maximum;
}
改进的直接法： 注意到 Sum[i, …, j]= Sum[i, …, j-1]+A[j]，则可以将算法中的最后一个for循环省略，避免重复计算，从而使得算法得以改进，改进后的算法复杂度为 O ( N 2 ) O(N^2) O(N2)：
int MaxSum(int* A, int n){
int maximum=-INF;
int sum;
for(int i=0;i<n;i++){
sum=0;
for(int j=i;j<n;j++){
sum+=A[j];
if(sum>maximum)
maximum=sum;
}
}
return maximum;
}
分治算法： 把问题分解为两个规模减半的子问题，再采用一次遍历算法。 总的时间复杂度为 T ( N ) = O ( N ∗ l o g 2 N ) T(N)=O(N*log_2N) T(N)=O(N∗log2N)
问题规模减半的相同子问题，可以通过递归求得。
跨越中间元素的处理方法: 两个子数组分别为 (A[0],…,A[n/2-1]) 和 (A[n/2],…,A[n-1]) 跨越中间元素的情况只要找到以A[n/2-1]结尾的最大数组和 s 1 = s u m ( A [ i ] , . . . , A [ n / 2 − 1 ] ) ( 0 ≤ i < n 2 − 1 ) s_1=sum(A[i],...,A[n/2-1]) (0leq i < frac{n}{2}-1) s1=sum(A[i],...,A[n/2−1])(0≤i<2n−1)与以 A[n/2] 开始的最大数组和 s 2 = s u m ( A [ n / 2 ] , . . . , A [ j ] ) ( n 2 ≤ j < n ) s_2=sum(A[n/2],...,A[j]) (frac{n}{2} leq j < n) s2=sum(A[n/2],...,A[j])(2n≤j<n)。那么这种情况下的最大值为 s 1 + s 2 = A [ i ] + . . . + A [ n / 2 − 1 ] + A [ n / 2 ] + . . . + A [ j ] s_1+s_2=A[i]+...+A[n/2-1]+A[n/2]+...+A[j] s1+s2=A[i]+...+A[n/2−1]+A[n/2]+...+A[j]，只需对原数组进行一次遍历即可。
动态规划： 选与不选A[0] 考虑数组的第一个元素A[0]，以及和最大的一段数组 (A[i],…,A[j]) 跟 A[0] 之间的关系，有以下几种情况：
- 当 0=i=j 时，元素 A[0] 本身构成和最大的一段；
- 当 0=i<j时，和最大的一段以 A[0] 开始；
- 当 0<i 时，元素A[0] 跟和最大的一段没有关系。
m a x { A [ 0 ] , A [ 0 ] + S t a r t [ 1 ] , A l l [ 1 ] } max{ A[0], A[0]+Start[1], All[1]} max{ A[0],A[0]+Start[1],All[1]}
int max(int x, int y) //返回x,y两者中较大的值
{
return (x>y)?x:y;
}
int MaxSum(int* A,int n)
{
Start[n-1]=A[n-1];
All[n-1]=A[n-1];
for(i=n-2;i>=0;i--) //从数组末尾往前遍历，直到数组首
{
Start[i]=max(A[i], A[i]+Start[i+1]);
All[i]=max(Start[i],All[i+1]);
}
return All[0]; //遍历完数组，All[0]中存放着结果
}
上述方法的时间复杂度已经降到 O ( N ) 了 。 O(N)了。 O(N)了。
思考：上述代码额外申请了两个数组All[]，Start[]，能否在空间方面节省一些？
进一步改进只需要 O ( 1 ) O(1) O(1)的空间
int max(int x, int y) //返回x,y两者中较大的值
{
return (x>y)?x:y;
}
int MaxSum(int* A,int n)
{
//要做参数检查
nStart=A[n-1];
nAll=A[n-1];
for(i=n-2;i>=0;i--) //从数组末尾往前遍历，直到数组首
{
nStart=max(A[i], A[i]+nStart);
nAll=max(nStart,nAll);
}
return nAll;
