> # 动态规划——最大连续子序列和
## 一维最大连续子序列和
- [x] LeetCode 53 Maximum Subarray
- [x] HDU 1024 Max Sum Plus Plus
设$d[i]$表示以序列中$s[i]$结尾的最大连续子序列和,状态转移方程:
$$
d[i] = \max{d[j - 1] + s[i], s[i]} \quad 1 \leq i \leq n \\
target = \max(d[i])
$$
```c++
int maxSubArray(vector& nums) {
int tmpSum, maxSum;
tmpSum = maxSum = nums[0];
for (int i = 1; i < nums.size(); ++i){
tmpSum = max(tmpSum + nums[i], nums[i]);
maxSum = max(maxSum, tmpSum);
}
return maxSum;
}
```
## 最大子矩阵(二维情形)
- [x] 一本通-1282:最大子矩阵
这道题还可以和二分进行结合,比如求二维矩阵里子矩阵和不超过K的最大和。
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。
比如,如下4 × 4的矩阵
```
0 -2 -7