定(可能有负数)整数序列A1, A2, A3..., An,求这个序列中子序列和的最大值。(为方便起见,如果所有整数均为负数,则最大子序列和为0)。
13条回答 默认 最新
关注 - 代码已全部改成C风格,
- 代码已C测试通过
- 已经加上题解和思路
- 又不会可以记叙文
可以参考我的:https://blog.csdn.net/qq_33957603/article/details/80554648
以及代码提交(验证正确)地址:http://www.joyoi.cn/problem/tyvj-1305
###传统的做法是,枚举(只要对的话就够了
如果n<=10^3,我们很容易写出枚举(s是前缀和,区间[l,r]的和就是s[r]-s[l-1]。枚举l,r即可。#include<stdio.h> #define maxn 300010 #define max(a,b) (a>b?a:b) int a[maxn], q[maxn]; long long s[maxn], ans; int main(){ int n, m; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } for(int i = 1; i <= m; i++)//枚举长度 for(int j = i; j <= n; j++)//枚举r ans = max(ans, s[j]-s[j-i]);//可以算出l printf("%d\n",ans); return 0; }
###如果需要更快的,,,可以考虑用单调队列
- 如果右端点是i,那么就转为求一个左端点j属于[i-m,i-1]并且s[j]最小。并且j越靠近m一定是越优的(在后面更不容易超过m。
- 所以选择集合一定是,“下标位置递增,对应前缀和s也递增”的序列,我们可以用队列保存这个序列。
#include<stdio.h> #define max(a,b) (a>b?a:b) #define maxn 300010 using namespace std; int a[maxn], q[maxn]; long long s[maxn], ans; int main(){ int n, m; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } int l = 1, r = 1; q[l] = 0; //save j for(int i = 1; i <= n; i++){ while(l<=r && q[l]<i-m)l++; ans = max(ans, s[i]-s[q[l]]); while(l<=r && s[q[r]]>s[i])r--; q[++r] = i; } printf("%d\n",ans); return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么
- ¥15 banner广告展示设置多少时间不怎么会消耗用户价值
- ¥16 mybatis的代理对象无法通过@Autowired装填
- ¥15 可见光定位matlab仿真
- ¥15 arduino 四自由度机械臂
- ¥15 wordpress 产品图片 GIF 没法显示
- ¥15 求三国群英传pl国战时间的修改方法
- ¥15 matlab代码代写,需写出详细代码,代价私
- ¥15 ROS系统搭建请教(跨境电商用途)
- ¥15 AIC3204的示例代码有吗,想用AIC3204测量血氧,找不到相关的代码。