53. 最大子序和

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

進階:
如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

• 1-暴力：n^2
• 2-DP：
  a.分治（子問題） max_sum(i) = Max(max_sum(i - 1), 0) + a[i]
  b.狀態(tài)數(shù)組: f[i]
  c.DP方程:f[i] = Max(f[i - 1] , 0) + a[i]

1. dp問題：
   dp公式：dp[i] = max(nums[i] , nums[i] + dp[i - 1])
   提取出nums[i] ：dp[i] = max( 0 , dp[i - 1]) + nums[i]
   //nums[i - 1]代表dp[i - 1]
   nums[i] = max(0 , nums[i - 1]) + nums[i]

2. 最大子序和 = 當前元素自身最大（負的），或者 包含之前（正的）后最大

參考：
https://leetcode-cn.com/problems/maximum-subarray/solution/javashi-xian-dong-tai-gui-hua-fang-fa-by-zhengzhon/

https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; // 存儲以i為結(jié)尾的最大子序列和
        dp[0] = nums[0]; // 第0個元素最大序列和為nums[0]
        int maxSum = nums[0]; // 最大子序列和
        // 遍歷整個素組，獲取以i為結(jié)尾的最大子序列和
        // 當dp[i-1]>0時，dp[i]=nums[i]+dp[i-1]
        // 當dp[i-1]<=0時,dp[i]=nums[i]
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            // 每次比較dp[i]和maxSum取最大值
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

簡化if else 判斷：

    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length]; // 存儲以i為結(jié)尾的最大子序列和
        dp[0] = nums[0]; // 第0個元素最大序列和為nums[0]
        int maxSum = nums[0]; // 最大子序列和
        // 遍歷整個素組，獲取以i為結(jié)尾的最大子序列和
        // 當dp[i-1]>0時，dp[i]=nums[i]+dp[i-1]
        // 當dp[i-1]<=0時,dp[i]=nums[i]
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(0, dp[i - 1]) + nums[i];
//          if (dp[i - 1] > 0) {
//              dp[i] = dp[i - 1] + nums[i];
//          } else {
//              dp[i] = nums[i];
//          }
            // 每次比較dp[i]和maxSum取最大值
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

不新增dp數(shù)組，直接使用nums數(shù)組

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // 最大子序列和
        for (int i = 1; i < nums.length; i++) {
            nums[i] = Math.max(0, nums[i - 1]) + nums[i];
            maxSum = Math.max(maxSum, nums[i]);
        }
        return maxSum;
    }

對于上面的代碼，也可以使用lastSum來記錄nums[i-1]為結(jié)尾的最大連續(xù)子序列和

    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // 最大子序列和
        int lastSum = nums[0];//假設當前索引為i,則lastSum保存以nums[i-1]為結(jié)尾的最大連續(xù)子序列和
        // 遍歷整個素組，獲取以nums[i]為結(jié)尾的最大子序列和
        for (int i = 1; i < nums.length; i++) {
            lastSum = Math.max(0, lastSum) + nums[i];
            maxSum = Math.max(maxSum, lastSum); // 每次比較lastSum和maxSum取最大值
        }
        return maxSum;
    }