[Leetcode] Maximum Subarray 子序列最大和

summerpxy 发布于2019-08-14 16:11 / 3295人阅读

摘要：最新更新请见原题链接动态规划复杂度时间空间思路这是一道非常典型的动态规划题，为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。而最大子序列和的算法和上个解法还是一样的。

Maximum Subarray 最新更新请见：https://yanjia.me/zh/2019/02/...

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.

原题链接

动态规划 复杂度

时间 O(N) 空间 O(N)

思路

这是一道非常典型的动态规划题，为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。这里我们从后向前、从前向后计算都是可以的。在从前向后计算的方法中，我们将第i个元素之前最大的子序列和存入一个一维数组dp中，对第i+1个元素来说，它的值取决于dp[i]，如果dp[i]是负数，那就没有必要加上它，因为这只会拖累子序列的最大和。如果是正数就加上它。最后我们再讲第i+1个元素自身加进去，就得到了第i+1个元素之前最大的子序列和。

代码

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = dp[i-1]>0? dp[i-1] + nums[i] : nums[i];
            max = Math.max(dp[i],max);
        }
        return max;
    }
}

扫描算法 复杂度

时间 O(N) 空间 O(1)

思路

仔细观察上面的代码，我们其实只用到了dp[i-1]这个量，所以如果用一个变量记录上次的值，那么这O(N)的空间是可以省略的。我们要做的就是扫描一遍数组，遍历每个数的时候都更新这个变量。而最大子序列和的算法和上个解法还是一样的。

代码

public class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum = sum < 0 ? nums[i] : sum + nums[i];
            max = Math.max(sum, max);
        }
        return max;
    }
}

混合云私有云最大子序列最长递增子序列最长公共子序列动态规划子序列代码

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

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

leetcode53 Maximum Subarray 最大连续子数组

摘要：我们可以分别得出这三种情况下的最大子数列和，并比较得出最大的那个。我们只需要考虑左子列的最大和以及跨越了左右的中子列的最大值。题目要求 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given ...

Bamboy 2019-08-14 18:08 评论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
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
leetcode 643 Maximum Average Subarray I

摘要：题目详情输入一个数组和一个整数。要求找出输入数组中长度为的子数组，并且要求子数组元素的加和平均值最大。题目详情 Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need ...

SwordFly 2019-08-15 13:57 评论0 收藏0
[LintCode/LeetCode] Maximum Product Subarray

摘要：这是一道简单的动规题目，同步更新数组解决了为负数的问题。即使是求最小乘积子序列，也可以通过取和的最小值获得。 Problem Find the contiguous subarray within an array (containing at least one number) which has the largest product. Example For example, g...

meteor199 2019-08-14 15:21 评论0 收藏0