問題描述：
給定整數(shù)（可以為負數(shù)），A1勇凭，A2掂铐，A3,....,AN,求子序列最大的值
舉例：
對于整數(shù)列-1,11,-4,13,-5,-2， 最大的序列值為20 子序列為(11,-4,13)
算法1（樓主首先想到的辦法,時間復雜度為：O(n2)）：
解析：遍歷此序列缩赛，取得每個小子序列的值，比較撰糠，最后得到最大的序列值，生成以下子序列并取得所有子序列和
-1
-1,11
...
-1,11辩昆，-4,13阅酪，-5，-2
11
11，-4
...
11术辐，-4,13砚尽，-5，-2
...
實現(xiàn)：
public static int maxSubSum2(int [] iargs){ int sum=0; for(int i=0;i<iargs.length;i++){ int thissum=0; for(int j=i;j<iargs.length;j++){ thissum+=iargs[j]; if(thissum>sum){ sum=thissum; } } } return sum; }
算法2（算是小大招辉词，時間復雜度為O(nlogn)）：
解析：在我們例子中必孤，最大的子序列可能存在三個部分，（左邊部分瑞躺、右邊部分敷搪、左邊一部分+右邊一部分），如下表所示：
| 左邊部分 | 右邊部分 |
|---|---|
| -1,11,-4 | 13,-5,-2 |
左邊部分最大子序列為：11幢哨，右邊部分最大子序列為13赡勘，左邊+右邊最大子序列為20,（11,-4,13）
實現(xiàn)：
public static int maxSubSum3(int[] a,int left,int right){ int sum=0; if(left==right){ sum=a[left]>0?a[left]:0; return sum; } int center=(left+right)/2; int leftMax=maxSubSum3(a,left,center); int rightMax=maxSubSum3(a,center+1,right); int maxLeftBorder=0,leftBorderSum=0; for(int i=center;i>=left;i--){ leftBorderSum+=a[i]; if(maxLeftBorder<leftBorderSum){ maxLeftBorder=leftBorderSum; } } int maxRightBorder=0,rightBordeSumr=0; for(int i=center+1;i<=right;i++){ rightBordeSumr+=a[i]; if(maxRightBorder<rightBordeSumr){ maxRightBorder=rightBordeSumr; } } return max3(leftMax,rightMax,maxLeftBorder+maxRightBorder); } public static int max3(int a,int b,int c){ int cen=a>b?a:b; return c>cen?c:cen; }
算法3（大招，時間復雜度為O(n),不看源碼想不到捞镰，修煉不夠罢⒂搿）：
解析：
假設a[i]為負數(shù)，則a[i]不可能為此子序列的起始岸售，同理践樱，若a[i]到a[j]的子序列為負，則a[i]到a[j]不可能為子序列的起始凸丸，則可以從a[j+1]開始推進拷邢，
實現(xiàn)：
public static int maxSubSum4(int a[]){ int thisMax=0,maxSum=0; for(int i=0;i<a.length;i++){ thisMax+=a[i]; if(thisMax>maxSum){ maxSum=thisMax; } if(thisMax<0){ thisMax=0; } } return maxSum; }
算法三 只對數(shù)據(jù)進行一次掃描，一旦a[i]被讀入并處理甲雅，它就不再需要被記憶解孙。因此數(shù)組可以被按順序讀入，在主存中不必存儲數(shù)組的任何部分抛人。具有這種特性的算法叫聯(lián)機算法(on-line algorithm)弛姜，僅需要常量空間并以線性時間運行的聯(lián)機算法幾乎是完美算法！
以下為pytho版實現(xiàn)
def maxSubSum1(*a): max=0 for i,value in enumerate(a): thisMax=0 for j in a[i:]: thisMax+=j if thisMax>max : max=thisMax return max def maxSubSum2(left,right,*a): if left==right: #base case return a[left] center =(left+right)/2 maxLeft=maxSubSum2(left,center,*a) maxRight=maxSubSum2(center+1,right,*a) leftSum=0 maxLeftSum=0 i=center while i>=0: leftSum+=a[i] if leftSum>maxLeftSum: maxLeftSum=leftSum i=i-1 rightSum = 0 maxRightSum = 0 i = center+1 while i <=right : rightSum += a[i] if rightSum > maxRightSum: maxRightSum = rightSum i = i + 1 return max(maxLeft,maxRight,maxLeftSum+maxRightSum) def max(*a): max=0 for i in a: if i>max: max=i return max def maxSubSum3(*a): max=0 thisMax=0 for i in a: thisMax+=i if thisMax>max: max=thisMax if thisMax<0: thisMax=0 return max
若想取得源碼妖枚，請參看github
java版本源碼
python版本源碼
