原题T53 最大子序和
对于这道题目，因为从来没有接触过动规的做法，所以我苦思冥想，最后只能写出了一个的暴力解法，然后在最后一组数据成功超时。
以下正解
动规应该是最优解法，同时贪心和分治也能够解决题目，但是目前只对动规有了较深的理解，至于贪心和分治日后再补。
为什么要用动态规划？
原题中提示了时间复杂度应该为O(n)，而暴力解法无法达到这个要求。同时，题目中“最大”，“连续”也引导用动规的思想来解决问题。
怎么用动规？
[-2,1,-3,4,-1,2,1,-5,4] 对于这个数组，我们依次向后遍历，前一个元素小于0时，就跳过他。而前一个元素大于0时，就把他与当前元素合并，成为一个新的元素。因为当前一个元素大于0时，代表当前这个子序和正在增大，而一旦前一个元素小于0时，代表子序和正在减小，而它一定不是我们要的子序和。
[-2, 1, -2, 4, 3, 5, 6, 1, 5]
很显然，数组中的最大项就是我们要的答案。只需取出数组中的最大元素就好了。
小细节
正如我之前所述，我们总是从前一个元素来判断，所以边界条件就是数组内只有一个元素，单独拿出来即可。
附上代码
class Solution {
public:
int maxSubArray(vector& nums) {
if(nums.size() == 1)return nums[0];
for(int i = 1; i < nums.size(); i ++ ){
if(nums[i - 1] < 0)continue;
else nums[i] += nums[i - 1];
}
sort(nums.begin(), nums.end());
return nums[nums.size() - 1];
}
};
时间复杂度，空间复杂度
