动态规划 字节跳动
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  1. 输入: [-2,1,-3,4,-1,2,1,-5,4],
  2. 输出: 6
  3. 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划

可以从4往前看。 4所在的位置的最大和的连续子数组，为-5位置的最大和连续子数组和零的较大值 加上自己，所以就可以总结出：

  1. 子问题：problem(i) = max(problem(i-1), 0) + a[i]
  2. 状态数组：f[i]
  3. DP方程：f[i] = max(f[i - 1] , 0) + a[i] ```cpp class Solution { public: int maxSubArray(vector& nums) {
    1.  int len = nums.size();
    2.  if (len == 1) return nums[0];
    3.  vector<int>dp(len, 0);
    4.  dp[0] = nums[0];
    5.  int maxNums = dp[0];
    6.  for (int i = 1; i < len; i++) {
    7.      dp[i] = max(dp[i-1], 0) + nums[i];
    8.      if (dp[i] > maxNums) {
    9.          maxNums = dp[i];
    10.      }
    11.  }
    12.  return maxNums;
    } }; //改进 主要是把dp[i] = max(dp[i-1], 0) + nums[i]; 拆成把上一个结果和零比较，就能改成空间复杂度为O(1) class Solution { public: int maxSubArray(vector& nums) {
    1.  int len = nums.size();
    2.  if (len == 1) return nums[0];
    3.  int m = nums[0];
    4.  int maxNums = m;
    5.  for (int i = 1; i < len; i++) {
    6.      m = max(m, 0) + nums[i];
    7.      if (m > maxNums) 
    8.          maxNums = m;
    9.  }
    10.  return maxNums;
    } };

```