https://leetcode.cn/problems/maximum-subarray/

法一

  • 子数组以 i 位置结尾
    • 可能性1） [i] 自己
    • 可能性 2） 不止[i] 
      1.    - [ i ] + dp[i -1]
      1. public int maxSubArray(int[] nums) {
      2. int max = nums[0];
      3. int N = nums.length;
      4. // dp[i] : 数组以i位置结尾时的最大结果是多少
      5. int[] dp = new int[N];
      6. dp[0] = nums[0];
      7. for (int i = 1; i < N; i++) {
      8.     int p1 = nums[i];
      9.     int p2 = nums[i] + dp[i - 1];
      10.     dp[i] = Math.max(p1, p2);
      11.     max = Math.max(max,  dp[i]);
      12. }
      13. return max;
      14. }
      优化
      1. public int maxSubArray1(int[] nums) {
      2. int max = nums[0];
      3. int N = nums.length;
      4. int prev = nums[0];
      5. for (int i = 1; i < N; i++) {
      6.    int p1 = nums[i];
      7.    int p2 = nums[i] + prev;
      8.    prev = Math.max(p1, p2);
      9.    max = Math.max(max,  prev);
      10. }
      11. return max;
      12. }

      法二

      ```java public int maxSubArray2(int[] nums) { int max = Integer.MIN_VALUE; int cur = 0; for (int i = 0; i < nums.length; i++) { cur += nums[i]; max = Math.max(max, cur); cur = cur < 0 ? 0 : cur; } return max; }

```