最大连续子序列和：递归和动态规划

雨点打透心脏的1/2处 2022-06-12 05:54 196阅读 0赞

**问题描述：**

**给定一个整数序列，a0, a1, a2, …… , an（项可以为负数），求其中最大的子序列和。如果所有整数都是负数，那么最大子序列和为0；**

方法一：

用了三层循环，因为要找到这个子序列，肯定是需要起点和终点的，所以第一层循环确定起点，第二层循环确定终点，第三层循环在起点和终点之间遍历。时间复杂度：O(N^3)

package secondCHA;
    
    public class maxSUM1 {
    
    	static int MaxSubSequence( int A[]){  
    	    int ThisSum,MaxSum,i,j,k;  
    	    int N=A.length;
    	    MaxSum = 0;  
    	    for(i=0;i<N;i++)  
    	    {  
    	        for(j=i;j<N;j++)  
    	        {  
    	            ThisSum = 0;  
    	            for(k=i;k<=j;k++)  
    	            {  
    	                ThisSum += A[k];  
    	            }  
    	            if(ThisSum > MaxSum)  
    	                MaxSum = ThisSum;  
    	        }  
    	    }  
    	    return MaxSum;  
    	}   
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
             int[] a={4,-3,5,-2,-1,2,6,-2};
             System.out.println(MaxSubSequence(a));
    	}
    
    }

方法二：

只用了两层循环，相当于是第一层用来找到每个可能的子序列的起点，而第二个循环直接从第一层确定的起点往数组结尾遍历，在遍历的过程中同时也计算序列值。前两种方法都是穷举法，都是把所有可能的子序列都找出来，然后计算值再和最大值比较。

package secondCHA;
    
    public class maxSUM2 {
    	static int MaxSubSequence( int A[]){  
    		int N=A.length;
    	    int ThisSum,MaxSum,i,j;  
    	    MaxSum = 0;  
    	    for(i=0;i<N;i++)  
    	    {  
    	        ThisSum = 0;  
    	        for(j=i;j<N;j++)  
    	        {  
    	            ThisSum += A[j];  
    	            if(ThisSum > MaxSum)  
    	                MaxSum = ThisSum;  
    	        }  
    	    }  
    	    return MaxSum;  
    	}  
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		  int[] a={4,-3,5,-2,-1,2,6,-2};
    	      System.out.println(MaxSubSequence(a));
    	}
    
    }

方法三：

用到了递归，用到了这样一种思想，当然要我肯定想不到，纯属借鉴了：

对于一数字序列，其最大连续子序列和对应的子序列可能出现在三个地方。或是整个出现在输入数据的前半部（左），或是整个出现在输入数据的后半部（右），或是跨越输入数据的中部从而占据左右两半部分。前两种情况可以通过递归求解，第三种情况可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大和（包含后半部分的第一个元素）而得到，然后将这两个和加在一起即可。

主要从递归的角度分析，把问题分为了小问题，处理的过程都一样，嗯，所以就用递归了。然后递归重要在于理解两步，过程和终点。

首先**分析终点**，子问题一步步被划分，最终，明显看出，**原始序列最终会被分为一个长度为1的子序列**（一个大于1的数一直除，肯定会到1的），把长度为1的子序列当成原问题，那么根据题意，如果是正数，就要，如果是负数，不如不要，就为0。所以，递归的终点设置得正确。

然后**分析过程**，分析递归的过程，在debug的过程中，你能发现，递归最开始是一直拆分子问题，直到到达递归终点再一层一层倒着返回调用结果。可以把递归过程看成一个**二叉树**，所以递归**终点就是此递归过程二叉树的最后一层**，而在以下程序中， MaxLeftSum = MaxSubSum(A,Left,Center); 这句就是左孩子，MaxRightSum = MaxSubSum(A,Center+1,Right);就是右孩子。而左孩子语句先执行，所以过程最开始一定是往**左下方向**直到第一个终点，观察程序中的数组，**第一个终点之前**前肯定是传递了一个\{4，-3\}的数组进去，再一分为二，然后传递\{4\}进去返回4，传递-3进去，返回0，再把他们左右序列最大值（因为两序列各只有一个，且这里必须包含左序列最右和右序列最左，所以这里就是这俩序列自身）加起来，为1。分析了这个问题的规模最小的问题，发现了这个递归的过程确实没有毛病。

理解了终点和过程，那么这个递归你也就理解了。

但是首先你得先想到这种思想，你才有前提写出这递归代码。

package secondCHA;
    
    public class maxSUM3 {
       
    	static int MaxSubSum( int A[], int Left, int Right)  
    	{  
    	    int MaxLeftSum,MaxRightSum;  
    	    int MaxLeftBorderSum,MaxRightBorderSum;  
    	    int LeftBorderSum,RightBorderSum;  
    	    int Center,i;  
    	      
    	    if(Left == Right)  
    	    {  
    	        if(A[Left] > 0)  
    	            return A[Left];  
    	        else  
    	            return 0;  
    	    }  
    	      
    	    Center = (Left + Right)/2;  
    	    MaxLeftSum = MaxSubSum(A,Left,Center);  
    	    MaxRightSum = MaxSubSum(A,Center+1,Right);  
    	      
    	    MaxLeftBorderSum = 0;  
    	    LeftBorderSum = 0;  
    	    for(i = Center;i >= Left;i--)  
    	    {  
    	        LeftBorderSum += A[i];  
    	        if(LeftBorderSum > MaxLeftBorderSum)  
    	            MaxLeftBorderSum = LeftBorderSum;  
    	    }  
    	      
    	    MaxRightBorderSum = 0;  
    	    RightBorderSum = 0;  
    	    for(i = Center+1;i <= Right;i++)  
    	    {  
    	        RightBorderSum += A[i];  
    	        if(RightBorderSum > MaxRightBorderSum)  
    	            MaxRightBorderSum = RightBorderSum;  
    	    }     
    	      
    	    return Max(MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum);  
    	}   
    	  
    	static int Max(int a, int b, int c)  
    	{  
    	    if(a>b&&a>c)  
    	        return a;  
    	    else if(b>a&&b>c)  
    	        return b;  
    	    else  
    	        return c;   
    	}  
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		 int[] a={4,-3,5,-2,-1,2,6,-2};
    		 int left=0;
    		 int right=a.length-1;
    		 System.out.println(MaxSubSum(a,left,right));
    	}
    
    }

方法四：

这种方法应该也算动态规划吧，毕竟把递归变成了非递归（但我这么理解不对，非递归不等于动态规划）。算法书说这是联机算法，特点是仅需要常量空间和线性时间运行。

重点还是在于理解算

1.只有一个for循环，循环里的j变量理解成序列的起点，但是这个起点有时会跳过若干数，当当前计算的序列a\[i\]到a\[j\]的和ThisSum**一旦**为负时，则ThisSum归零，因为for循环的循环变量加1，则从a\[j+1\]开始加和，即起点跳到了负数和的子序列的下一个数字。

2.理解这样的事实，一个子序列必然是以正数开头的，因为如果以负数开头，那么去掉这个子序列，那得到一个更优解。

3.还有这么个事实，一个子序列，如果**一旦**他的前若干个数字组成的新的个数更少的子序列的和为负数，那么去掉这个子序列，便能得到了一个更优解。

4.MaxSum若遇到更大的和则更新，若遇到更小的和，则不更新（没有动作）。ThisSum则充分利用了第二个事实，当某个时刻子序列为负数，则归零即相当于去掉了这子序列所有数字，从下一个数字从新开始加和。

5.其实第二个事实，不是那么好理解，关键在于，去掉是当一旦出现了和为负数（**之前的和都是>=0的，但是加了下一个数后和就为负数了**）的子序列，就去掉这个子序列，而且这时，子序列最后一个数肯定为负数，因为是没加最后一个数时和还为正数，但一加上了就变成负数，所以这最后一个数肯定是负数。假设这个负数为a\[i\],现在归零了，从a\[i+1\]开始加和了，**思考以****a\[i\]为结果的刚才去掉的这个序列（这里指去掉的子序列的任意数到这个序列的最后一个数，的这些所有可能的子序列，因为是要求连续，所以是任意到结尾的某个序列考虑是否该加回去）是不是不该去掉呢**，为了证明，我们可以从去掉的序列的最后一个a\[i\]（第一种可能是只有最后那个数）开始加回去，你会加上a\[i\]，因为a\[i\]是负数，所以加了和反而变小了，不该加。如果加上a\[i-1\]和a\[i\]呢，a\[i-1\]和a\[i\]的和肯定也是负数，这个负数可能比a\[i\]小，也可能大但肯定是个负数（举例：1,2，-5和2，-1，-5），前者是大一点的负数，后者是小一点的负数，**但是必然的，加回去的序列和肯定还是负数，共同点是-5是造成序列和变成负数的那个第一个数，同理可得从任意处开始到结尾的序列的和必须也是负数，即是所有这些可能的序列都不应该加回去**。——所以，一旦序列和为负数，那么这个序列就应该去掉了。（不会出现这种情况，比如去掉这个子序列2,1，-5,1（和为-1），因为当i移动到-5时，就已经去掉了，也证明了去掉的子序列的最后一个数是负数）

package secondCHA;
    
    public class maxSUM4 {
    	static int MaxSubSequence( int A[])  
    	{  
    		int N=A.length;
    	    int ThisSum,MaxSum,j;  
    	    ThisSum = MaxSum =0;  
    	    for(j = 0;j < N;j++)  
    	    {  
    	        ThisSum += A[j];  
    	          
    	        if(ThisSum > MaxSum)  
    	            MaxSum = ThisSum;  
    	        else if(ThisSum < 0)  
    	            ThisSum = 0;   
    	    }  
    	    return MaxSum;   
    	}   
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		  int[] a={4,-3,5,-2,-1,2,6,-2};
    	      System.out.println(MaxSubSequence(a));
    	}
    
    }