return max(maxLeftSum,maxLeftBorderSum+maxRighttBorderSum,maxRightSum);
}
//可变参数的使用，jdk1.5及以上
public int max(int ...args)
{
int max=args[0];
for(int i=1;i
return max;
}
}
package com.kiritor;
/**
* 分治+递归的思想求解
* 时间复杂度降为O(NlogN)
* @author Kiritor
*/
public class MaxSub {
public int maxSub(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 maxLeftSum= maxSub(a,left,center);//左边递归
int maxRightSum = maxSub(a,center+1,right);//右边递归
//处理中间包含center左右边界的最大和情况
int maxLeftBorderSum = 0,leftBoderSum = 0;
for(int i=center;i>=left;i--)
{
leftBoderSum +=a[i];
if(maxLeftBorderSum
}
int maxRighttBorderSum = 0,rightBoderSum = 0;
for(int i=center+1;i<=right;i++)
{
rightBoderSum +=a[i];
if(maxRighttBorderSum
}
//问题合并(治)
return max(maxLeftSum,maxLeftBorderSum+maxRighttBorderSum,maxRightSum);
}
//可变参数的使用，jdk1.5及以上
public int max(int ...args)
{
int max=args[0];
for(int i=1;i
return max;
}
}
Tisp:需要注意的是子问题之间是不包含公共的子问题的。
算法四
最后提供一种比较“聪明”的算法，其时间复杂度为O(N)，它只对数据进行一次扫描。
[java]
/**线性时间，复杂度为O(N)*/
public int maxSubLinear(int[] a)
{
int sum = 0,maxSum =0;
for(int i=0;i
sum +=a[i];
if(sum>maxSum)
maxSum =sum;
else if(sum<0)
sum = 0;//如果sum<0,就没有必要将前面的序列继续代入了，将sum=0
}
return 0;
}
/**线性时间，复杂度为O(N)*/
public int maxSubLinear(int[] a)
{
int sum = 0,maxSum =0;
for(int i=0;i
sum +=a[i];
if(sum>maxSum)
maxSum =sum;
else if(sum<0)
sum = 0;//如果sum<0,就没有必要将前面的序列继续代入了，将sum=0
}
return 0;
}