动态规划(状态转移方程)

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

1
输入：nums = [1]
2
输出：1

1
输入：nums = [5,4,-1,7,8]
2
输出：23

1
int maxSubArray(vector<int>& nums) {
2
  if(nums.empty())
3
    return 0;
4
  vector<int> v(nums);//将vector类型nums全部复制到v中去
5
  int maxNum = nums[0];
6
  for(int i = 1; i < nums.size(); i++)
7
  {
8
    v[i] = max(v[i - 1] + nums[i], nums[i]);
9
    if(maxNum < v[i])
10
      maxNum = v[i];
11
  }
12
  return maxNum;
13
}