求环中的最长连续子序列的和

xiaoxiao2021-02-28  80

1282: ykc想吃好吃的 这里写链接内容

题目描述

一天,ykc在学校闲的无聊,于是决定上街买点吃的,ykc很懒,本来就不是很像逛街,于是找来了czl帮他买,这里应该有滑稽,而czl也不愿为ykc买东西吃,但是ykc很强势,非让他去买,呢没办法了,然而czl还有很多事要做,没呢么多时间帮ykc,而这条小吃街又很长,有n家店,n有50000这么大,并且这n家店的商品价值有所不同(要知道,商品的价值可能为负,哈哈,很神奇吧,但是czl肯定不会傻到赔钱,所以你懂的),哇,czl要疯了,他不想逛这么久啊,他还有个毛病,他只会连续的逛若干家店,并且由于这条街的店很多,所以肯定不会是一条直线,换句话说就是首尾相连,即第n家店和第一家店是连在一起的,然而ykc希望czl买的东西价值最大,不然就会不开心,于是他就把艰难的任务交给你了,他真的不想浪费时间,你能帮助他吗? 输入

第1行:小吃街的长度N(2 <= N <= 50000) 第2 - N+1行:N个整数,代表每个店的商品价值 (-10^9 <= S[i] <= 10^9) 输出

czl能买到的最大价值 样例输入

6 -2 11 -4 13 5 -2 样例输出

25

思路:1. 可以求出最大连续子序列的和and最小连续子序列的和,然后最后max(总和-最小连续和, 最大连续和),2. 也可以取数组的相反数求两个最大连续子序列的和。

#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int inf = 0x3f3f3f3f; const int MAXN =100005; typedef long long LL; LL a[MAXN]; int main() { int n; while(~scanf("%d",&n)) { LL sum=0; for(int i=1; i<=n; ++i) { scanf("%lld", &a[i]); sum+=a[i]; } LL ans=0, Max=-inf; LL Min=inf, ans1=0; for(int i=1; i<=n; ++i) { if(ans+a[i]<0) ans=0; else ans+=a[i]; if(ans1+a[i]>0) ans1=0; else ans1+=a[i]; Min=min(ans1, Min); Max=max(ans, Max); } printf("%lld\n",max(sum-Min, Max)); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-47338.html

最新回复(0)