蓝桥杯算法提高VIP-和最大子序列（C++描述）只做最好的思路！

1262 阅读 8 评论 0 点赞

这题看起来好像挺简单的，暴力枚举不就完事了？代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int max=a[0];
	for(int i=0;i<n-1;i++){
		int sum=a[i];
		for(int j=i+1;j<n;j++){
			sum+=a[j];
			if(sum>max){
				max=sum;
			}
		}
	}
	if(max<a[n-1]){
		max=a[n-1];
	}
	cout<<max<<endl;
	return 0;
}
```
什么？？？时间超限50%！看来只能试试dp来做了，代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100005],dp[100005],res=-10005;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
    //对于当前这个数，可以选择加入总和，或者舍去之前的总和选取当前这个数作为新的总和。
		dp[i]=max(dp[i-1]+a[i],dp[i]);
		res=max(dp[i],res);
	}
	cout<<res<<endl;
	return 0;
}
```
利用dp的思想，再思考思考~咦？？真的不可以枚举吗？还是可以枚举的！只是思路要变一变，代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
	int n,sum=0,max=-10005;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	//对于当前这个数，加入总和后若一旦使sum为负，立即置0处理，也就是从下一个数开始重新对sum计数求和，这样就在保留了sum为负之前的最大max的同时又可以不影响接下来可能超过前面max的max数值所可能的交换。
		sum+=a[i];
		if(max<sum){
			max=sum;
		}
		if(sum<0){
			sum=0;
		}
	}
	cout<<max<<endl;
	return 0;
}
```

0.0分

14 人评分

本文分类：题解列表
浏览次数：1262 次浏览
发布日期：2020-04-16 12:57:09
本文链接：https://blog.dotcpp.com/a/69488

上一篇 > 蓝桥杯算法提高VIP-最大乘积-题解(C++代码)
下一篇 > [编程入门]自定义函数之整数处理-题解(C++代码)

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

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

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

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

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

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

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

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

评论列表共有 8 条评论

: 故园无此声 2月前回复TA
妙

: kelecat 8月前回复TA
有操作的哥们

: 董丕通 10月前回复TA
@yue @sxyue .......

: yue 2年前回复TA
@yue 最大子序列不是{3，-2，3}吗

: wht 2年前回复TA
@yue 你这个案例，此时最大子序列就是5啊，怎么会是4呢

: yue 2年前回复TA
第三个代码有bug 如果样例为3 -2 3 -5 5的话，正确最大子序列和为4，而带入代码答案为5

: 打碎一池星月 2年前回复TA
dp那个解法，dp[i]=max(dp[i-1]+a[i],dp[i])应该改成dp[i]=max(dp[i-1]+a[i],a[i]);

: 简 3年前回复TA
厉害

蓝桥杯算法提高VIP-和最大子序列 （C++描述）只做最好的思路！

求球的体积

用while循环，卡住终止点是更新后的a=0 ；不断用10求模，不断更新，循环输出

【编程入门】自定义函数处理最大公约数与最小公倍数

年龄与疾病

评论列表 共有 8 条评论

发表评论 取消回复

蓝桥杯算法提高VIP-和最大子序列（C++描述）只做最好的思路！

评论列表共有 8 条评论

发表评论取消回复