最大连续子段和

最近在学习动态规划，将自己的所思所想所得记录下来，检验自己是否真正懂了。

 

问题描述：

给定一个数组，记录一串数字，可正可负，现要求出其中最大的连续子段和。

 

用数组A[N]记录所要求的数组，用数组B[N]来记录连续子段和的状态

通过分析，可以知道：

当B[K]>0时，无论B[K]为何值，B[K]=B[K-1]+A[K]

当B[K]<0时，也就是B[K]记录到一个A[J]是负的，可以把B[K]变成负的，那么B[J]记录的这一段应该截掉，应为无论后面的A[K]多大，加上个负数总不可能是最大的子段和，因此将B[K]=A[K]，重新开始记录。

 

故动态转移方程便可得出

B[K] = MAX(B[K-1]+A[K] , A[K])

 

看个实例

k      1       2       3        4
a[k]  3     -4       2        10
b[k]  3     -1       2        12

 

必须记住B[K]是状态量，要获得最大连续子段和，只需在数组B中扫描一遍得到最大的数即可。

 一个有N个整数元素的一维数组{A[0],A[1],....,A[N-1],A[N]},这个数组有很多连续的子数组，那么连续子数组之和的最大的一个的值是什么？

   先给出一个时间复杂度为O(N^2)的求解程序实现，思想很简单，就是遍历数组中所有的子数组，代码如下：

[java] view plaincopy

/** 

 * 计算数组的最大子序列 

 * @author win7 

 * 

 */  

public class MaxSubArraySum {  

      

    public static int sumN2(int [] array){  

        int sum=0,maxSum=Integer.MIN_VALUE;  

        int n=array.length;  

        int count=0;  

        for(int i=0;i<n;i++){  

            sum=0;  

            for(int j=i;j<n;j++){  

                sum+=array[j];  

                if(sum>maxSum){  

                    maxSum=sum;  

                }  

                count++;  

            }  

        }  

        System.out.println("length="+n+"||count="+count);  

        return maxSum;  

    }  

    public static void main(String [] args){  

//      System.out.println("MIN_VALUE="+Integer.MIN_VALUE);  

        int [] array={-5,-2,-3,-5,-3,-2};  

        int sum=MaxSubArraySum.sumN2(array);  

        System.out.println("最大子序列和="+sum);  

    }  

  

}  

因为子数组求和满足动态规划的后无效特性，所以可以使用动态规划的思想，从分治的算法中得到提示：可以考虑数组的第一个元素A[0]，以及最大的一段数组(A[i],...A[j])跟A[0]之间的关系，有一下几种情况：

1.当0=i=j时，元素A[0]元素本身构成和最大的一段；

2.当0=i<j时，和最大的一段以A[0]开始；

3.当0<i时，元素A[0]跟和最大的一段没有关系。

从上面的三种情况可以将一个大问题(N个元素的数组)转化为一个较小的问题(n-1个元素的数组)。假设知道(A[1],...,A[N-1])中包含A[1]的和最大的一段的和为start[1]。那么，根据上面分析的三种情况，不难看出(A[0],...,A[N-1])中问题的解all[0]是三种情况的最大值max{A[0],A[0]+start[1],all[1]}。通过问题分析，可以看到问题满足无后效性，可以使用动态规划的方法来解决。

程序代码实现如下：

[java] view plaincopy

/** 

 * 在时间复杂度为O(N)内找出数组中最大的子序列的累加和 

 * @param array 

 * @return 

 */  

public static int sumN(int [] array){  

    int n=array.length;  

    int all=array[n-1],start=array[n-1];  

    int count=0;  

    for(int i=n-2;i>=0;i--){  

        if((start+array[i])>array[i]){  

            start=start+array[i];  

        }else{  

            start=array[i];  

        }  

        if(all<start){  

            all=start;  

        }  

        count++;  

    }  

    System.out.println("数组长度="+array.length+"||时间复杂度="+count);    

    return all;  

总结

以上是生活随笔为你收集整理的最大连续子段和的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。