[Leetcode] Maximum Subarray 子序列最大和

summerpxy 發(fā)布于2019-08-14 16:11 / 3392人閱讀

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

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.

原題鏈接

動態(tài)規(guī)劃 復雜度

時間 O(N) 空間 O(N)

思路

這是一道非常典型的動態(tài)規(guī)劃題，為了求整個字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。這里我們從后向前、從前向后計算都是可以的。在從前向后計算的方法中，我們將第i個元素之前最大的子序列和存入一個一維數(shù)組dp中，對第i+1個元素來說，它的值取決于dp[i]，如果dp[i]是負數(shù)，那就沒有必要加上它，因為這只會拖累子序列的最大和。如果是正數(shù)就加上它。最后我們再講第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)的空間是可以省略的。我們要做的就是掃描一遍數(shù)組，遍歷每個數(shù)的時候都更新這個變量。而最大子序列和的算法和上個解法還是一樣的。

代碼

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