问题描述：
给定整数（可以为负数），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
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)，仅需要常量空间并以线性时间运行的联机算法几乎是完美算法！
以下为pytho版实现
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版本源码
网友评论