[Leetcode] Maximum Subarray 子序列最大和

summerpxy 發布于2019-08-14 16:11 / 3399人閱讀

摘要：最新更新請見原題鏈接動態規劃復雜度時間空間思路這是一道非常典型的動態規劃題，為了求整個字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個解法還是一樣的。

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;
    }
}

GPU云服務器云服務器最大子序列最長遞增子序列最長公共子序列動態規劃子序列代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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