题目53:连续子数组的最大和
输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
分析
动态规划思想,使用一个数组dp,dp[i]表示以nums[i]结尾的连续子数组的最大和,所以可以列出如下方程式:
- dp[0] = nums[0];
- dp[i] = dp[i-1] + nums[i]; 如果dp[i-1] > 0
- dp[i] = nums[i]; 如果dp[i-1] <= 0
代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp;// dp[i]表示以nums[i]结尾的连续子数组的最大和
dp.resize(nums.size());
for (std::size_t i = 0, size = nums.size(); i < size; ++i) {
if (i == 0) {
dp[0] = nums[i];
continue;
}
if (dp[i-1] <= 0) {
dp[i] = nums[i];
} else {
dp[i] = dp[i-1] + nums[i];
}
}
int max_value = INT_MIN;
for (auto i : dp) {
max_value = max(max_value, i);
}
return max_value;
}
};
网友评论