最大子序列和的線性時間解法

問題描述：給定整數A1，A2,...An(可能有負數)。求 

的最大值。（如果所有的整數都是負數，則最大子序列和為0。）

程式代碼：

int maxSubSum(const vector<int>&a)
{
	int maxSum = 0;
	int thisSum = 0;
	for(int i = 0;i < a.size();i++)
	{
		thisSum += a[i];//新讀取一個數
		if(thisSum > maxSum)//這次的結果比最大序列還大
		{
			maxSum = thisSum;
		}
		if(thisSum < 0)//推進i
		{
			thisSum = 0;
		}
	}
	return maxSum;
}
           

解釋：

1.最大子序列的第一個元素不會是負的。即，如果a[i]是負的，那麼它不可能是最大子序列的起點。因為任何用a[i]開頭的序列，此時都不如用a[i+1]開頭的序列和大。

2.同理，任何負的子序列都不可能是最優子序列的字首。即，如果我們在内循環中檢測到a[i]到a[j]的和是負的，那麼我們可以推進i，關鍵的結論是我們不光可以推進到i+1，實際上我們可以直接推進到j+1。說明：令p是i+1到j之間的任何一個下标，因為j下标是第一個使從a[i]開始的序列變負的下标，是以，從a[i]到a[p]的序列和為正數。也就是說任何從p開始的子序列，都不如這個序列再加上a[i]到a[p-1]這個序列的和大。是以我們可以直接推進到j+1。

通過這個例子我們可以發現，許多聰明的算法，運作時間是明顯的，本例是O(N)，但是正确性不是那麼明顯。