LC : https://leetcode-cn.com/problems/maximum-subarray/
牛客:https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&&tqId=11183&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
思路和算法:
**
假设 nums 数组的长度是 n,下标从 0 到 n−1。
我们用 代表 nums[i],用 代表以第 ii个数结尾的「连续子数组的最大和」,那么很显然我们要求的答案就是:
公式 :
因此我们只需要求出每个位置的 ,然后返回 f 数组中的最大值即可。那么我们如何求呢?我们可以考虑
单独成为一段还是加入对应的那一段,这取决于 和+ 的大小,我们希望获得一个比较大的,于是可以写出这样的动态规划转移方程:
代码
class Solution {
public:
int maxSubArray(vector<int> &num) {
int maxValue = num[0];
int pre=0;
for (int i = 0; i < num.size(); ++i) {
pre = max(pre + num[i], num[i]);
maxValue = max(maxValue, pre);
}
return maxValue;
}
};