题解 | 最大序列和
思路：用动态规划，dp[i]表示前i个元素的最大序列和，如果前面累加的和为负数或0，则不计入当前元素前缀最大和；否则加入；
#include<stdio.h>
#include<algorithm>
using namespace std;
long long s[1000001];//存含n个元素的序列
long long dp[1000002];//元素的取值范围 [−10^9,10^9],设成全局变量
int main() {
int n;//范围1<=n<=10^6
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lld", &s[i]);
}
dp[1] = s[0];
long long maxcnt = dp[1];
for (int i = 2; i <= n; i++) {
if (dp[i - 1] <= 0) {
dp[i] = s[i - 1];//等于第i个元素
}
else {
dp[i] = dp[i - 1] + s[i - 1];//前i-1个元素的最大序列和+第i个元素
}
maxcnt = max(dp[i], maxcnt);//更新最大
}
printf("%lld\n", maxcnt);
return 0;
}
计算机复试机试（王道版） 文章被收录于专栏
收录王道2026年计算机复试机试的（课程）代码题解，仅供个人学习参考
字节跳动公司福利 1371人发布
查看8道真题和解析