方法介绍
方法一：三重循环。
方法二：二重循环
方法三：分治。对原序列，取中间为分界点，分成左右两半，最大子序列S恰有三种情况：完全落在左半部分（可递归求解）， 完全落在右半部分（可递归求解），跨两半。对于跨两半的情况，把最大子序列分成左右两段L和R， 注意左段L一定是以分界点为终点的最大子序列（否则若L’>L则S’=L’+R>L+R=S矛盾），即可以从分界点开始向左扫描一遍求出L。
方法四：动态规划。对于以i为终点（包括i）的最大子序列S，恰有三种情况： S长0，依定义和为0，因max初始0， 可以不考虑；S长1；S长>=2，此时一定是以i-1为终点的最大子序列再添加元素i。
方法五：求最大子序列，就是找两点，使起点和终点间积分最大；在积分序列中看，就是使 (终点值-起点值)最大。 给定终点，起点应为终点前的最小值。从头到尾扫描积分序列，O(1)更新迄今为止最小值thisMin， 当前值-thisMin即以当前点为终点的最大子序列。也可给定起点，终点应为起点后的最大值，程序改为从后向前扫描。
代码实现
package testtt;
public class Tee {
//方法一
public static int maxSum1(int [] a){
int maxSum=0;
for(int i=0;i<a.length;i++)
for(int j=i;j<a.length;j++){
int thisSum=0;
for(int k=i;k<=j;k++){
thisSum+=a[k];
}
if(thisSum>maxSum){
maxSum=thisSum;
}
}
return maxSum;
}
//方法二，该算法运行时间为O(n^2)
public static int maxSum2(int [] a){
int maxSum=0;
for(int i=0;i<a.length;i++){
int thisSum=0;
for(int j=i;j<a.length;j++){
thisSum+=a[j];
if(thisSum>maxSum){
maxSum=thisSum;
}
}
}
return maxSum;
}
//方法三，该算法时间复杂度为O(NlogN)
public static int max3(int a,int b,int c){
int maxnumber=Math.max(a, b);
return Math.max(c, maxnumber);
}
public static int maxSum3(int [] a,int left,int right){
if(left==right)
if(a[left]>0){
return a[left];
}else{
return 0;
}
int center=(left+right)/2;//二分
int maxSumLeft=maxSum3(a,left,center);//求出左半部分的最大子序列和
int maxSumRight=maxSum3(a,center+1,right);//求出右半部分最大子序列的和
int maxBorderLeft=0;int leftBorder=0;//包含左半部分最后一个数的最大值求解
for(int i=center;i>=left;i--){
leftBorder+=a[i];
if(leftBorder>maxBorderLeft){
maxBorderLeft=leftBorder;
}
}
int maxBorderRight=0;int rightBorder=0;//包含右半部分第一个数的最大值求解
for(int i=center+1;i<=right;i++){
rightBorder+=a[i];
if(rightBorder>maxBorderRight){
maxBorderRight=rightBorder;
}
}
return max3(maxSumLeft,maxSumRight,maxBorderLeft+maxBorderRight);
}
//方法四，联机算法 该算法时间复杂度为O(n)
public static int maxSum4(int [] a){
int maxSum=0;int thisSum=0;
for(int i=0;i<a.length;i++){
thisSum+=a[i];
if(thisSum>maxSum){
maxSum=thisSum;
}else if(thisSum<0){
thisSum=0;
}
}
return maxSum;
}
//方法五
public static double f5( double [] a, int mOff, int mLen ) {
int n = a.length;
double cum[] = new double[n];
if( n > 0 )
cum[0] = a[0];
for( int i=1; i<n; i++ )
cum[i] = cum[i-1] + a[i]; // cum[i] means cummulate [0,i]
double max = 0;
double thisMin = 0;
int off = -1;
for( int i=0; i<n; i++ ) {
if( cum[i] < thisMin ) { // min cum[0,i]
thisMin = cum[i];
off = i;
}
double thisMax = cum[i] - thisMin; // max [,i]
if( thisMax > max ) {
max = thisMax;
// (off, i]
mOff = off + 1;
mLen = i - off;
}
}
return max;
}
static int [] a={-1,-2,5,6,3,-1,10};
static double [] b={-1,-2,5,6,3,-1,10};
public static void main(String args[]){
int firstsum=maxSum1(a);
int secondsum=maxSum2(a);
int thirdsum=maxSum3(a,0,a.length-1);
int forthsum=maxSum4(a);
double fifthsum = f5(b,3,3);
System.out.print(firstsum+"\n"+secondsum+"\n"+thirdsum+"\n"+forthsum+"\n"+fifthsum);
}