解题思路:这个用的动态规划,从第一个数遍历到最后一个数,时间复杂度就是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.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论