一、遍歷所有可能情況
(1234...N)所有可能子序列如下：
1；12；123......
2；23；234......
......
N
共N趟，沒趟可能的情況由N，N-1...，1依次遞減。
時間復雜度O(N3)的算法：
int MaxSubsequenceSum( const int A[ ] , int N)
{
int MaxSum = 0;
for(int i = 0; i < N; i++) ?//控制趟數為N
//每趟可能的子序列和有以下兩個循環控制。
for(int j = i; j < N; j++) ?//控制每趟的開始位置
{
int sum = 0;
for(int k = j; k < N; k++)
{
sum += A[k];
if(sum > MaxSum)
MaxSum = sum;
}
}
return MaxSum;
}
二、時間復雜度O(N2)
不考慮程序跑的趟數，直接羅列所有情況
int MaxSum = 0;
for(i = 0; i < N; i++)
{
sum = 0;
for(j = i; j < N; j++)
{
sum += A[j];
if(MaxSum < sum)
MaxSum = sum;
}
return MaxSum;
}
三、相對復雜度O(N*logN)遞歸算法
分而治之：將問題分解為兩個大小大致相等的子問題——分；兩個子問題的解合并到一起并再做些少量附加工作，最后得到整個問題的解——治。
最大子序列可能出現的位置為數據的左半邊，數據的右半邊，數據的中部。
從概率論的角度來解讀就是找出事件的完備事件組，將情況分為兩類：1、包含中間元素；2、不含中間元素。其中不含中間元素又分左右側兩種情況。
int MaxSubsequenceSum( const int A[ ], int N)
{
return MaxSubSum(A, 0, N-1); ? //增加邊界的參數
}
static int MaxSubSum( const int A[ ], left, right)
{
if(left == right)
if(A[left] > 0)
return A[left];
else return 0;
int center = (left + right)/2;
int MaxLeftSum = MaxSubSum(A, left, center);
int?MaxRightSum = MaxSubSum(A, left, center);
int maxLeftSum = 0;
for(int i = center; i >= left; i--)
{
int?leftSum += A[i];
? ?if(maxLeftSum < leftSum)
maxLeftSum = leftSum;
}
int maxRight = 0;
for(int j = center; j <=right; j--)
{
int rigthSum += A[j];
if(maxRightSum < rightSum )
maxRightSum = rightSum;
}
return Max3(MaxLeftSum, MaxRightSum, maxRightSum+maxLeftSum);
}
int Max3(a,b,c)
{
return a > (b>c?b:c)?a:(b>c?b:c);
}
四、時間復雜度O(N)
1、如果sum<0，將sum置0，maxSum不更新，即maxSum從序列中首正數開始記錄；
2、將求和的幾個元素看做一個單元組，包含首正數的單元組中出現大于首正數時，更新maxSum，即maxSum=sum，此時maxSum存放當前最大子序列和；
3、當有負數出現時，sum<maxSum，maxSum不更新。當sum<0時，該單元組整體為一個負數，其后每個單元組包含該單元組都是負增長，故將sum置0，maxSum不更新；
int MaxSubsequenceSum( const int A[], int N)
{
int sum = 0; int maxSum = 0;
for(int i = 0 ; i < N; i++)
{
sum += A[i];
if(maxSum < sum)
? maxSum = sum;
else if(sum < 0)
? ?sum = 0;
}
return maxSum;
}
