题目地址：点击打开链接
1282: ykc想吃好吃的
时间限制: 1 秒
内存限制: 128 MB
提交: 688
解决: 85
提交
状态
题目描述
一天，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～n 数 从1开始找往后找 sum1记录不首尾相连 如果出现和小于零 则置为0
从此处往后找 用sum2记录最小的值 用总的sum-sum2 可得首尾相连的最大值
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
long long num[50050];
long long sum=0,sum1=0,sum2=0,M=0,N=0;
for(int i=0;i<n;i++)
{
scanf("%lld",&num[i]);
sum+=num[i];//记录总值
sum1+=num[i];//记录不含首尾相连的最大值
sum2+=num[i];//记录不好首尾相连的最小值
M=max(M,sum1);
N=min(N,sum2);//
if(sum1<0)
sum1=0;
if(sum2>0)
sum2=0;
}
printf("%lld\n",max(M,sum-N));//sum-N为含首位相连的最大值
}
return 0;
}
