解题思路:这个用的动态规划,从第一个数遍历到最后一个数,时间复杂度就是O(n)
这个题重点就是要求是最大子序列,那么从前往后的子序列中出现子序列为小于等于0
就说明这个子序列是没意义不能要的
因为加上这个子序列就不满足最大的子序列了
明白这个相信这个题也就迎刃而解了
注意事项:
参考代码:
#include
using namespace std;
//求最大子段和算法
int MaxSum(int* a, int n) {
int sum = 0, b = 0;
for (int i = 1; i <= n; i++) {
if (b > 0) {
b += a[i];//如果大于0,就说明可以加
}
else {//如果b<=0,就说明之前放的子序列都没意义,因为要求子段和最大
b = a[i];
}
if (b > sum) {//更新最大值
sum = b;
}
}
return sum;
}
int main() {
int a[100], n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cout << MaxSum(a, n) << endl;
return 0;
}
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复