官方地址：https://leetcode-cn.com/problems/maximum-subarray/
问题描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
基本事实
穷举算法思路：选1个组合的最大值，选2个任意组合的最大值，直到选n个组合的最大值，最后再求最大值，时间复杂度比较高 n*CnM
dp规律思路：一直累加(只要累加的结果是正数)，每次累加的结果比已经保存的结果大，就更新保存的结果（就是最大和），如果累加的结果为负，则从下一个元素重新开始累加，直到最后一个元素
初始值
- 最大和初始为：数组第一个元素
- 累加器初始值：数组第一个元素
算法实现
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int currentMaxSum = nums[0];
int totMaxSum = nums[0];
for (int i = 1; i < nums.size(); i ++) {
if (currentMaxSum <= 0) {
currentMaxSum = nums[i];
} else {
currentMaxSum += nums[i];
}
totMaxSum = max(totMaxSum, currentMaxSum);
}
return totMaxSum;
}
};
一些注意的点
动态规划(Dynamic Planning)的题一般都是状态转移公式比较难推导，一旦公式找到了，实现就比较简单了，如果没有找到状态转移公式，就算最简单的动态规划也是很难用代码写出来的。