算法一：窮舉式地嘗試所有的可能

int maxSubsequenceSum(const int a[], int n){ int i, j, k; int thisSum, maxSum = 0; for (i = 0; i < n; i++)?? ? ? ?for (j = i; j < n; j++)?? ? ? ?{?? ? ? ? ? ?thisSum = 0;?? ? ? ? ? ?for (k = i; k < j; k++)?? ? ? ? ? ? ? ?thisSum += a[k];?? ? ? ? ? ?if (thisSum > maxSum) maxSum = thisSum; } return maxSum;}

算法復雜度為O(n^3)（三重for循環）

算法二：算法一的改進

int maxSubsequenceSum(const int a[], int n){ int i, j; int thisSum, maxSum = 0; for (i = 0; i < n; i++)?? ?{?? ? ? ?thisSum = 0;?? ? ? ?for (j = i; j < n; j++)?? ? ? ?{?? ? ? ? ? ?thisSum += a[j];?? ? ? ? ? ?if (thisSum > maxSum) maxSum = thisSum; } } return maxSum;}

該算法去除了算法一中不必要的計算，時間復雜度為O(n^2)（兩重for循環）。

算法三：分治（divide-and-conquer）策略

分治策略：

分：把問題分成若干個（通常是兩個）規模相當的子問題，然后遞歸地對它們求解。

治：將若干個問題的解4合并到一起并可能再做少量的附加工作，最后得到整個問題的解。

在這個問題中，最大子序列和可能在三處出現：即左半部序列、右半部序列、穿過中部從而占據左右兩半部分的序列。前兩種情況可以通過遞歸求解。而遞歸的基準情況（base cases）是序列只有一個元素（left == right），若該元素大于0，則返回該元素，否則返回0。第三種情況的最大和可以通過分別求出左邊部分（包含左半部分最后一個）的最大和以及右邊部分（包含右邊部分的第一個）的最大和，再將它們相加得到。

int maxSubsequenceSum(const int a[], int left, int right)

{

int i, mid, maxLeftSum, maxRightSum;

int maxLeftBorderSum, leftBorderSum;

int maxRightBorderSum, rightBorderSum;

if (left == right) { /*基準情況*/

if (a[left] >= 0)

return a[left];

else

return 0;

}

mid = left + (right - left) / 2;

maxLeftSum = maxSubsequenceSum(a, left, mid); /*左半部分的最大和*/ maxRightSum = maxSubsequenceSum(a, mid+1, right); /*右半部分的最大和*/

/*下面求穿過中點的最大和*/

maxLeftBorderSum = 0, leftBorderSum = 0;

for (i = mid; i >= left; i--)

/*中點及其以左的最大和*/

{

leftBorderSum += a[i];

if (leftBorderSum > maxLeftBorderSum)

maxLeftBorderSum = leftBorderSum;

}

maxRightBorderSum = 0, rightBorderSum = 0;

for (i = mid+1; i <= right; i++) ? /*中點以右的最大和*/?

{

rightBorderSum += a[i];

if (rightBorderSum > maxRightBorderSum)

maxRightBorderSum = rightBorderSum;

}

/*返回三部分中的最大值*/

return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum);

}

int max3(int a, int b, int c)

{

int maxNum = a;

if (b > maxNum)

maxNum = b;

if (c > maxNum)

maxNum = c;

return maxNum;

}

以序列2，4，-1，-5，4，-1為例，其左半部分最大和為2 + 4 = 6；右半部分最大和為4，穿過中心的最大和為（-1 + 4 + 2）+ （-5 + 4）= 0。故該序列的最大子序列和為max（6，4，0）= 6。時間復雜度分析:假設T(n)為求解大小為n的最大子序列和問題所花費的時間。當n = 1是，T(1) = O(1)；當n > 1時，兩次遞歸花費的總時間為2T(n/2),兩個并列的for循環花費的時間是O(len(left)+len(right)) = O(n)，一共為2T(n/2)+O(n)。綜上可列如下方程組：

T(1) = 1T(n) = 2T(n/2) + O(n)

事實上，上述方程組常常通用于分治算法，由方程組可算出T(n) = O(nlogn)。

算法四：

算法三利用遞歸較好的解決了最大子序列和問題，但仔細分析，在遞歸過程中，同一個元素很可能多次被操作，有沒有更高效的算法？先上代碼

int maxSubsequenceSum(const int a[], int n){ int i; int maxSum, thisSum; maxSum = thisSum = 0; for (i = 0; i < n; i++)?? ?{?? ? ? ?thisSum += a[i];?? ? ? ?if (thisSum > maxSum) maxSum = thisSum; else if (thisSum < 0)?? ? ? ? ? ?thisSum = 0;?? ?}?? ?return maxSum;?}

可以簡單的分析出上述代碼的時間復雜度是O(n),比前三種都高效。它為什么是正確的？從直觀上理解：首先for循環的if語句保證了每次更新后最大和保存在maxSum中，而我們從i = 0開始掃描，假設掃描到i = t(t < n)，且此時的最大和已經保存在maxSum中，而當前的和（thisSum）如果大于0，不管當i > t的元素大小如何，加上thisSum總會使之后的和變大，而如果thisSum小于0，肯定會使之后的和變小，既然還會變小，那干脆就重新來過（thisSum = 0），有些另起爐灶的意味。

該算法一個附帶的優點是，它只對數據進行一次的掃描，一旦a[i]被讀入并被處理，它就不再需要記憶。因此，如果數組在磁盤或磁帶上，它就可以被順序讀入，在主存中不必儲存數組的任何部分。不僅如此，在任意時刻，該算法都能對它已經讀入的數據給出子序列問題的正確答案（其他算法即前三種不具有這個特性）。具有這種特性的算法叫做聯機算法（online algorithm）。僅需要常量空間并以線性時間運行的online algorithm幾乎是完美的算法。————《數據結構與算法分析》（中文版第二版）