怎么求出一个数组最大的连续累加之和呢？方法有很多，我们目前只讲一个比较不错的方法，该方法使用了分治递归的思想。
我们假设下面是我们需要计算的数组，其中A是游标，我可以知道游标将数组分成了两段，最大值有可能出现在前半段也有可能出现在后半段，还有一种情况是跨越A（中间）相加的一段。
[1,-3,5,7 A,9,-8,6,2]
跨越A相加的部分我们可以这样计算：
int maxLeftBorderSum =0;
int leftBorderSum =0;
for (int i = center;i >= left;i--){
leftBorderSum += array[i];
if (leftBorderSum>maxLeftBorderSum){
maxLeftBorderSum = leftBorderSum;
}
}
int maxRightBorderSum =0;
int rightBoederSum =0;
for (int i = center +1;i <= right;i++){
rightBoederSum += array[i];
if (rightBoederSum>maxRightBorderSum){
maxRightBorderSum = rightBoederSum;
}
}
以中间为起点向两边相加，然后将左右两边最大和相加：maxLeftBorderSum+maxRightBorderSum，即可得跨越A相加最大的。
前后端最大值可以通过递归求得：
int center = (left + right)/2;
int maxLeftSum =maxSumRec(array,left,center);
int maxRightSum =maxSumRec(array,center+1,right);
最后我们分析一下这个递归方法的基准方法：
if (left == right){
if (array[left]>0){
return array[left];
}else {
return 0;
}
}
因此完整的程序是：
public static void main(String[] args)throws Exception {
int[] array = {1,-5,4,6,-7,3,2,-5,9};
System.out.println("结果："+maxSumRec(array,0,array.length-1));
}
public static int maxSumRec(int[] array,int left,int right){
if (left == right){
if (array[left]>0){
return array[left];
}else {
return 0;
}
}
int center = (left + right)/2;
int maxLeftSum =maxSumRec(array,left,center);
int maxRightSum =maxSumRec(array,center+1,right);
int maxLeftBorderSum =0;
int leftBorderSum =0;
for (int i = center;i >= left;i--){
leftBorderSum += array[i];
if (leftBorderSum>maxLeftBorderSum){
maxLeftBorderSum = leftBorderSum;
}
}
int maxRightBorderSum =0;
int rightBoederSum =0;
for (int i = center +1;i <= right;i++){
rightBoederSum += array[i];
if (rightBoederSum>maxRightBorderSum){
maxRightBorderSum = rightBoederSum;
}
}
return max(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
}
public static int max(int v1,int v2,int v3){
if (v1>v2){
return v1>v3?v1:v3;
}else {
return v2>v3?v2:v3;
}
}
最后返回三者的最大值即可求得。
这种算法算是效率比较高的，但是根据合成效益法则可知，这个算法仍然有重复计算的部分。
下面说的这种算是则不会出现这种情况，只会对数组进行一次扫描。
public static void main(String[] args) throws Exception {
int[] array = {1,-5,4,6,-7,3,2,-5,9};
System.out.println("结果："+maxSubSum(array));
}
public static int maxSubSum(int array[]){
int thisSum = 0;
int maxSum = 0;
for (int i = 0;i<array.length;i++){
thisSum += array[i];
if (thisSum>maxSum){
maxSum = thisSum;
} else if (thisSum<0){
thisSum = 0;
}
}
return maxSum;
}
这种算法是仅需要常量空间并以线性时间运行的联机算法。
网友评论