【C语言】连续子数组的最大和
贪心DP,数组长度优化
题目描述
输入一个 非空 整型数组,数组里的数可能为正,也可能为负。
数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
样例
输入:[1, -2, 3, 10, -4, 7, 2, -5]
输出:18
算法
贪心
dp[ i ] 表示以 nums[ i ] 结尾的子数组的和最大值。
每次考虑下一个数 nums[ i + 1 ] 来更新 dp[ i + 1 ] ,有两种情况,
第一种,dp[ i ] < 0,那么 dp[ i + 1 ] 直接为 nums[ i + 1 ];
第二种,dp[ i ] >= 0, 所以 dp[ i + 1 ] 为 dp[ i ] + nums[ i + 1 ];
用 max 函数求出 dp[ i + 1 ] 两种情况中的最大值。
ans 每次更新为从 0 到 i 的nums数组的所有子数组的和的最大值。
当 i 枚举到 n 时,ans 即为最终答案。
最后,max函数求两数的较大值。
代码如下
int max(int a, int b){
return a > b ? a : b;
}
int maxSubArray(int* nums, int numsSize) {
int dp[1010], ans = nums[0]; dp[0] = nums[0];
for(int i = 1; i < numsSize; ++i){
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
ans = max(dp[i], ans);
}
return ans;
}
优化
然后观察,发现dp[]数组只用到了相邻的两个数更新,可以优化为长度为2的数组
时空复杂度
都为$O(n)$
C 代码
int max(int a, int b){
return a > b ? a : b;
}
int maxSubArray(int* nums, int numsSize) {
int dp[2], ans = nums[0]; dp[0] = nums[0];
for(int i = 1; i < numsSize; ++i){
dp[i % 2] = max(dp[(i - 1) % 2] + nums[i], nums[i]);
ans = max(dp[i % 2], ans);
}
return ans;
}