2150 装饰彩带
小于 1 分钟
2150 装饰彩带
【算法】 最大子段和、贪心
【C++】 一维数组、动态规划思想
【难度】 普及−
一、题目简述
给 个整数(,有正有负),求连续子段的最大和(最大子段和)。
二、解题思路
这是经典的最大子段和问题。贪心法:
- 遍历数组,维护当前子段和
sum - 如果
sum < 0,抛弃之前的子段,重新从当前元素开始(因为负前缀只会拖累后面的和) - 每步更新答案
ans = max(ans, sum)
手动模拟:[1, -2, 1, -3, 5, 6]
- i=1: sum=1, ans=1
- i=2: sum=-1,负数了,sum=0(抛弃)
- i=3: sum=1, ans=1
- i=4: sum=-2,sum=0
- i=5: sum=5, ans=5
- i=6: sum=11, ans=11 ✅
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int sum = 0, ans = -2e9; // ans 初始化为负无穷
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
sum += x;
ans = max(ans, sum);
if (sum < 0) sum = 0; // 负前缀抛弃
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间:
- 空间:
五、知识扩展
这是 Kadane 算法,也是动态规划的思想:dp[i] = max(a[i], dp[i-1] + a[i])。
