leetcode53 Maximum Subarray 最大连续子数组

Bamboy 发布于2019-08-14 18:08 / 1535人阅读

摘要：我们可以分别得出这三种情况下的最大子数列和，并比较得出最大的那个。我们只需要考虑左子列的最大和以及跨越了左右的中子列的最大值。

题目要求

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

即：寻找数列中的一个子数列，该数列中的值得和是所有子数列中最大的。

思路一：divide&conquer

我们可以从数列的中间节点将数列分为两个子数列，则最大的子数列要么在左子列，要么在右子列，要么跨越了左子列和右子列。我们可以分别得出这三种情况下的最大子数列和，并比较得出最大的那个。
divide&conquer即递归思路，将复杂问题分解为简单的小问题分别解决。递归的重点在于覆盖所有可能情况，并且覆盖到基类。

    public int maxSubArray(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        return maxSubArray(nums, start, end);
        
        
    }
    
    //递归调用该方法
    public int maxSubArray(int[] nums, int start, int end){
        if(start==end){
            return nums[start];
        }
        int mid = (start + end) / 2;
        //获得最大左子列
        int leftMax = maxSubArray(nums, start, mid);
        //获得最大右子列
        int rightMax = maxSubArray(nums, mid+1, end);
        
        //获得最大中子列
        int leftSumMax = Integer.MIN_VALUE;
        int temp = 0;
        do{
            temp += nums[mid];
            if(temp>leftSumMax){
                leftSumMax = temp;
            }
        }while((--mid)>=start);
        
        temp = 0;
        mid = (start + end)/2 + 1;
        int rightSumMax = Integer.MIN_VALUE;
        do{
            temp += nums[mid];
            if(temp>rightSumMax){
                rightSumMax = temp;
            }
        }while((++mid)<=end);
        int midMax = leftSumMax + rightSumMax;
        return Math.max(Math.max(leftMax, rightMax), midMax);
    }

思路二：divide&conquer2 recursion

上面是将数组从中划分为两个子数组,这里我们还可以划分为nums[n-1]和nums[n]。这样我们就可以将右子列的情况简化为直接返回右子列的值。我们只需要考虑左子列的最大和以及跨越了左右的中子列的最大值。所以我们需要记录两个值，第一个是当前最大和，还有一个是到nums[n-1]的最大子列和。

    public int maxSubArray(int[] A) {
        int n = A.length;
        //存储经过下标为i的最大子数列和，用于判断中子列
        int[] dp = new int[n];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        return max;    
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

专线服务 idc机房托管最大连续子串算法数组连续判断最大子序列算法最大子数列

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

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

leetcode_53 Maximum Subarray

摘要：如果单开元素加和更大判断前面的子数组和是不是小于。此元素就成为了子数组的第一个元素。每次操作都要判断，当前是否是最大值，更新值。题目详情 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given t...

y1chuan 2019-08-15 13:37 评论0 收藏0
动态规划法（八）最大子数组问题（maximum subarray problem）

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

jzman 2019-07-30 16:46 评论0 收藏0
[Leetcode] Maximum Subarray 子序列最大和

摘要：最新更新请见原题链接动态规划复杂度时间空间思路这是一道非常典型的动态规划题，为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。而最大子序列和的算法和上个解法还是一样的。 Maximum Subarray 最新更新请见：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

summerpxy 2019-08-14 16:11 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode152 Maximum Product Subarray

摘要：题目要求从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。比如数组的最大乘积子数组为思路与代码这题目考察了动态编程的思想。至于为什么还要比较，是因为如果是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。题目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 评论0 收藏0