問題描述：

一個數組，長度為N，數組元素有負有正，如{-1， 4， 6， -3， 7， -3， -3， 9}；我們可以清楚的知道最大的子數組應該是4到9，也就是下標1到下標7，和為17。

求解思路：

第一種方法：我們可以用定義1、兩個數ThisSum和MaxSum來記錄當前數組的和，以及數組的最大和。
2、我們可以用兩個for循環來來遍歷數組，每一次求出子數組的最大和，每個子數組從0開始，下一次遍歷子數組就是從1開始，以此類推。如第一次就【0~N-1】的最大和，第二次就是【1~N-1】,第三次就是【2~N】。。。。
3、這樣，每次用ThisSum來記錄當前數組的和，MAXSum來記錄當前子數組的最大和，與ThisSum比較，取其最大就能求出最大子數組的和。
4、還是看代碼吧，這樣比較好理解：

int MaxSubArraySum(int a[], int N, int &start, int &end)
{
	int ThisSum, MaxSum, i, j;
	*start = 0;
	*end = 0;
	MaxSum = 0;
	for (i = 0; i < N; ++i)
	{
		ThisSum = 0;
		for (j = i; j < N; ++j)
		{
			ThisSum += a[j];
			if (ThisSum > MaxSum)
			{
				*start  = i;
				*end = j;
				MaxSum = ThisSum;
			}
		}
	}

	return MaxSum;
}

5、此方法的時間復雜度很明顯為（O（N^2））
第二種算法： 思路：我們力求一種逼格最高的方法使得時間復雜度為（O(N)）. 1、同樣我們ThisSum來記錄當前子數組的和，MaxSum來記錄當前子數組最大和，我們可以從0位置開始便來，開始遍歷每次ThisSum 加上 a[ i ],如果當前ThisSum大於MaxSum的話，將ThisSum的值付給MaxSum，如果當前的ThisSum<0的話就把ThisSum的值賦值為0，接著下一步的遍歷。
2、這裡我必須說一下，求最大子數組的起點到尾端的求法， a、我們定義start 和end來記錄 b、當thisSum > maxSum時記錄end 等於此時的下標。 c、當thisSum < 0時，我們可以知道起點必須從新修改，改為下一個下標（i +1）為起點start，但是要小心下一個下標(i+1)可能 元素的值小於0，或者越界，所以我們必須判斷一下。如： if(i <= arr.length - 2 && arr[i+1] > 0){
start = i + 1;
} 我們可以寫出代碼：

int maxSubArraySum(int[] arr, int N, int &start, int end) {
		int maxSum = 0;
		int thisSum = 0;
		int i;
		*start = 0;
		*end = 0;
		for (i = 0; i < N; i++) {
			thisSum += arr[i];
			if (thisSum > maxSum){
				maxSum = thisSum;
				*end = i;
			}
			if (thisSum < 0){
				thisSum = 0;
				if(i <= N - 2 && arr[i+1] > 0){
					*start = i + 1;
				}
			}
				
		}
		//如果最大子數組不在數組裡面的話（數組元素全部<=0）,start,end賦值為-1
		if(*start == 0 && *end == 0 && arr[0] <= 0){
			*start = -1;
			*end = -1;
		}
		return maxSum;
	}

時間復雜度為（O（N））逼格滿滿有木有=＿=

最後一點總結：

在《數據結構與算法分析：C語言描述》中的第二章就出現這一道題，作者從（O（N^3））一路殺到（O(N)）,不得不佩服啊，有用循環和遞歸都有，今天我只講兩種比較典型的方法。
還有的就是作者沒有求出子數組的起點以及末端，我就裝逼求了一下，哈哈。