连续子数组的最大和

---

题目：

题解

1、前缀和算法

• 解题思路：所有 当前的前缀和 - 前面出现过的最小前缀和 的最大值（当前的前缀和去掉之前最小的前缀和，反而会变大，相当于之前的是累赘）

• 复杂度分析：

  • 时间复杂度O(n)
  • 空间复杂度O(1)

• 代码：

  // 前缀和算法
  public class Solution {
      public int maxSubArray(int[] nums) {
          int min = 0;
          int max = Integer.MIN_VALUE;
          int maxNums = 0;
          for (int i = 0; i < nums.length; i++) {
              maxNums += nums[i];
              // 所有 当前的前缀和 - 前面出现过的最小前缀和 的最大值
              // 当前的前缀和去掉之前最小的前缀和，反而会变大，相当于之前的是累赘
              max = Math.max(max,maxNums - min);
              min = Math.min(min,maxNums);
          }
          return max;
      }
  }

2、动态规划法

• 解题思路：

  • 第i+1个数，前i个数之和如果是正数，那么第i+1个数加上前i个数就会变大；如果是负数，则反转，那么前i+1个数就是nums[i+1]
  • 

• 复杂度分析：

  • 时间复杂度O(n)
  • 空间复杂度O(n)：状态数组的长度为N

• 代码：

  // 动态规划法
  class Solution2 {
      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]= Math.max(dp[i-1] + nums[i],nums[i]);
              max = Math.max(max,dp[i]);
          }
          return max;
      }
  }

• 滚动变量优化

  • 复杂度分析：

    • 时间复杂度O(n)
    • 空间复杂度O(1)

  • 代码：

    // 动态规划法(滚动变量优化）
    class Solution3 {
        public int maxSubArray(int[] nums) {
            int dp = 0;
            int max = nums[0];
            for (int num : nums) {
                dp = Math.max(dp + num,num);
                max = Math.max(max,dp);
            }
            return max;
        }
    }