最大子序列的求解-分治方法

microelec 发布于2019-08-16 14:37 / 1590人阅读

摘要：下面进行简单的作图分析注意到，递归函数从外层，沿着计算的路径，经过三次递归调用函数，到达基准，在基准层分别计算递归函数内部的三部分左侧最大子序列与右侧最大子序列的和，并利用求出最大者返回。

问题描述

问题：给定整数序列，求解其中最大子序列（连续的序列）。

思路分析

利用“分治”和递归的思想求解，在《数据结构与算法分析（Java语言描述）》Page29，作者给出了具体的java代码。
总体思路是，原序列的子序列存在于三处，左、右和跨中点。将序列从中点分割，分别用递归求出

左边最大子序列

右边最大子序列

跨中点的最大子序列

其中，步骤3分别求出包含左侧和右侧包含中点端点的最大子序列，求和即是结果。
这样最后三者中的最大者即为序列的最大子序列。

源程序

//添加了求三数最大值的函数
public class MaxSubsequence {

    public static int maxSubSum3(int[] a) {
        return maxSumRec(a,0,a.length-1);
    }
    
    private static int maxSumRec(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=maxSumRec(a, left, center);     //递归1
        int maxRightSum=maxSumRec(a, center+1, right); //递归2
        
        int maxLeftBorderSum=0,leftBorderSum=0;
        for(int i=center;i>=left;i--) {
            leftBorderSum+=a[i];
            if(leftBorderSum>maxLeftBorderSum)
                maxLeftBorderSum=leftBorderSum;            
        }
        
        int maxRightBorderSum=0,rightBorderSum=0;
        for(int i=center+1;i<=right;i++) {
            rightBorderSum+=a[i];
            if(rightBorderSum>maxRightBorderSum)
                maxRightBorderSum=rightBorderSum;            
        }
        
        return max3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);            
    }
    
    public static int max3(int a,int b,int c) {
        int temp=a>b?a:b;
        int max3=temp>c?temp:c;
        return max3;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr={4,-3,5,-2,-1,2,6,-2};
        int maxSubSum=maxSubSum3(arr);
        System.out.println("the maxSubSum of array arr is:"+maxSubSum);
    }

}

程序分析

程序中，maxSumRec为递归函数，函数开始为是否到达递归基准的if判断语句，然后分别是两个递归语句，执行步骤①②。对于递归而言，递归语句后边的语句暂时不执行，从递归语句处直接返回递归函数开始进行递归，在该递归语句处向内递归，直到到达基准语句，执行return跳出递归。递归语句计算出maxLeftSum和maxRightSum。

函数中，递归语句后边的部分计算步骤③，在for循环中，固定中点端点，分别向左右两侧循环求和，利用if语句来更新包含中心端点的maxLeftBorderSum和maxRightBorderSum。两个变量求和即是③的最大子序列。

最后，求出最大者即可。

启发：使用递归的时候，需要在递归语句前边，提前设置好到达基准的条件（if，return/break），以便适时完成递归，跳出递归函数。

程序性能分析

注意到，该段程序的两条递归语句出现在同一个函数内，起初我对递归的具体执行顺序理解错误，以为步骤①的递归执行得出maxLeftSum时，之后的步骤③语句并不会执行。实际进行程序调试后，发现，该段程序虽然看起来相对简洁，但在执行时，会执行不必要的语句，执行逻辑并不明了。

下面进行简单的作图分析：

注意到，递归函数从外层，沿着计算maxLeft的路径，经过三次递归调用maxSumRec函数，到达基准，在基准层分别计算递归函数内部的三部分maxLeft、maxRight、左侧最大子序列与右侧最大子序列的和maxLeftBorderSum+maxRightBorderSum，并利用max3求出最大者返回。然后再从基准层向上，计算上一层maxRightSum，然后依次规律，逐步向上计算，最后计算出整个递归函数的maxLeft、maxRight和左右和，最后再执行max3函数，返回三者的最大值，得到最终的最大子序列和。

整个过程类似二叉树的每一个节点都长三个不同大小的桃子，从根节点递归到最下层的树叶，比较三个桃子的大小，摘取一个，再摘取同辈的其他节点的桃子。依次向上摘，总体呈现从总到分，再从分到总的一个过程。

时间复杂度计算

程序主要运行部分在maxSumRec函数，分为if判断基准语句、两条递归语句、两个for计算半侧边界最大子序列语句。若序列元素个数为N，T（N）为该算法的运行时间。

在maxSumRec函数中，不管N为多少，if基准语句部分总是运行固定的常数时间。

若N=1，为基准情况，if语句执行，return返回结果，后续部分不再执行，因此，T（1）=1。

若N≠1，则后续的程序必须执行。两个for循环中，索引0~N-1的元素都被接触一次，运行时间为O（N）。if基准语句、与if等缩进的几条赋值语句运行时间为常量，与O（N）比可忽略。剩余为两条递归语句，每条语句执行时间为T（N/2）,因为左/右最大子序列求解，都是处理N/2大小的子序列。总的运行时间T（N）=2T（N/2）+O（N）。

参考书上的方法，使用规律递推的方式，计算T（N）。简化O（N）为N，并假设N为2的幂。T（2）=2×2，T（4）=4×3，T（8）=8×4，T（16）=16×5，若N=2^k，则T（N）=N(logN+1)=O（N log N）

总结

总体而言，对于计算序列的最大子序列而言，书中的本算法略显麻烦，后续会进行其他简洁方法的补充，本文借此算法来深入理解递归的过程。

云服务器 GPU云服务器最大子序列 js获取硬盘序列号的方法最长递增子序列最长公共子序列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73110.html

动态规划法（八）最大子数组问题（maximum subarray problem）

摘要：动态规划法用表示最大子数组的结束下标为的情形，则对于，有这样就有了一个子结构，对于初始情形，遍历就能得到这个数组，其最大者即可最大子数组的和。动态规划法想法巧妙，运行效率也高，但是没有普遍的适用性。问题简介本文将介绍计算机算法中的经典问题——最大子数组问题（maximum subarray problem）。所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续...

jzman 2019-07-30 16:46 评论0 收藏0
看动画轻松理解「递归」与「动态规划」

摘要：程序员小吴打算使用动画的形式来帮助理解递归，然后通过递归的概念延伸至理解动态规划算法思想。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。难点就在于找出动态规划中的这三个概念。在学习「数据结构和算法」的过程中，因为人习惯了平铺直叙的思维方式，所以「递归」与「动态规划」这种带循环概念（绕来绕去）的往往是相对比较难以理解的两个抽象知识点。...

cnio 2019-07-30 18:41 评论0 收藏0
算法导论笔记动态规划DP详解-钢条切割的分析与实现

摘要：假定出售一段长度为英寸的钢条的价格为单位，钢条长度均为整英寸。注若长度为英寸的钢条的价格足够大，最优解可能就是完全不需要切割。考虑长度为的情况，下图给出了英寸钢条的所有切割方案。 DP和分治的相似都是通过组合子问题的解来求解原问题。 DP中的programming指的是一种表格法，而非coding。 DP和分治的不同分治步骤：（例如归并排序）将问题划分为互不相交的子问题 ...

shinezejian 2019-08-14 17:51 评论0 收藏0
校招社招必备核心前端面试问题与详细解答

摘要：本文总结了前端老司机经常问题的一些问题并结合个人总结给出了比较详尽的答案。网易阿里腾讯校招社招必备知识点。此外还有网络线程，定时器任务线程，文件系统处理线程等等。线程核心是引擎。主线程和工作线程之间的通知机制叫做事件循环。 showImg(https://segmentfault.com/img/bVbu4aB?w=300&h=208); 本文总结了前端老司机经常问题的一些问题并结合个...

DevTalking 2019-08-02 15:31 评论0 收藏0