最大子序列问题

遇到这个问题不会，特地查找了一下相关的方法，在看到的方法中本文的第3个方法的代码思路清晰，相对于分治法虽然复杂度略高，但是有代码更简单更易写的优势

问题描述：
给定整数（可以为负数），A1，A2，A3,…,AN,求子序列最大的值
举例：
对于整数列-1,11,-4,13,-5,-2，最大的序列值为20 子序列为(11,-4,13)
算法1（楼主首先想到的办法,时间复杂度为：O(n2)）：
解析：遍历此序列，取得每个小子序列的值，比较，最后得到最大的序列值，生成以下子序列并取得所有子序列和

-1

-1,11

…

-1,11，-4,13，-5，-2

11，-4

…

11，-4,13，-5，-2

…
实现：

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）
实现：

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]为负数，则a[i]不可能为此子序列的起始，同理，若a[i]到a[j]的子序列为负，则a[i]到a[j]不可能为子序列的起始，则可以从a[j+1]开始推进，

实现：

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; 
}

算法三只对数据进行一次扫描，一旦a[i]被读入并处理，它就不再需要被记忆。因此数组可以被按顺序读入，在主存中不必存储数组的任何部分。具有这种特性的算法叫联机算法(on-line algorithm)，仅需要常量空间并以线性时间运行的联机算法几乎是完美算法！

以下为python版实现

# 此算法时间复杂度为O(n2)，也是最先想到的算法实现
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

#大招，使用递归实现算法，时间复杂度为：O(nlogn)
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)

#大大招，时间复杂度为：O(n)
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

if __name__=='__main__' :
    print maxSubSum1(-1,11,-4,13,-5,-2)
    print maxSubSum2(0,5,-1, 11, -4, 13, -5, -2)
    print maxSubSum3(-1, 11, -4, 13, -5, -2)