https://leetcode-cn.com/problems/maximum-subarray/
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
dp[0] = nums[0];
int max_value = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = (dp[i-1] > 0) ? nums[i] + dp[i-1]:nums[i];
max_value = (dp[i] > max_value) ? dp[i]:max_value;
}
return max_value;
}
};
思路
这个感觉和 300.最长上升子序列 有点像呀。
这个题目，暴力解的话，就是枚举所有的子数组呗，即（start, end）pair，复杂度O(n2)。
但是其实没必要暴力，因为有重复计算，举个例子，我计算sum(2,6)的时候，sum(2,5), sum(2,4)...可能都已经计算过了，但还要重复计算他们。因此，有没有可能找到重叠子问题，然后找递推关系呢？
手工填个表，模拟一下nums数组从1开始增长(即枚举end).
| 短文本 | 中等文本 | 稍微长一点的文本 |
|---|---|---|
| 稍微长一点的文本 | 短文本 | 中等文本 |
...
明天再写
