#动态规划
1. $dp_i$ 等于 以 $i$ 结尾的最大子数组和，$dp_0 = nums_0$，理解为只有一个数的数组时最大子数组和就是那一个元素
2. 当数组都为正数时，$dp_i = dp_{i-1} + nums_i$
3. 引入负数，当之前的结果小于等于零也就是 $dp_{i-1} <= 0$ 时可以抛弃掉直接取 $nums_i$，也就是 $dp_i = \cancel{dp_{i-1} +} nums_i = nums_i$
```cpp
class Solution {
public:
int maxSubArray(vector<int>&nums)
{
vector<int> dp = nums;
auto ans = dp[0];
for (int i = 1; i < nums.size(); i++)
{
if (dp[i - 1] > 0) dp[i] = dp[i - 1] + nums[i];
else dp[i] = nums[i];
ans = max(ans, dp[i]);
}
return ans;
}
};
```