3927Circular Sequence 思维题(求环形最大子列和)
Given a sequence with n elements, if the last element is also adjacent to the first element of the sequence, the sequence is called “circular sequence”.
Now, here comes a simple problem: given a circular sequence, you should find a segment of the sequence, such that it contains at least one element, and the sum of the elements is as large as possible.
输入
Input may contain several test cases. The first line is a single integer t, the number of test cases below. Each test case is composed of two lines. The first line of each test case is a positive integer n (1<=n<=100000), denoting the number of elements in the circular sequence, and the second line has n integers; the absolute value of each integer is no more than 100000.
输出
For each test case, output the maximum segment sum in a single line.
样例输入
2
2
-1 -2
3
1 -2 3
样例输出
-1
4
不考虑环:直接找非循环子序列maxsum1;
然后考虑循环:也就是两头相加情况,这是找非循环子序列minsum,把总和-minsum又得到一个maxsum2;
但前提的要有负数存在,负数不存在的话就直接是总和了;
否则就是max(maxsum1,maxsum2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100005];
int main()
{
int i,j,t,n;scanf("%d",&t);
while(t--){
scanf("%d",&n);
ll maxx=-0x3f3f3f3f,minn=0x3f3f3f3f;
ll sum=0,s=0;
int f=0;
for(i=0;i<n;i++){
scanf("%I64d",&a[i]);
if(a[i]>=0)f=1;
s+=a[i];
sum+=a[i];
maxx=max(maxx,sum);
if(sum<0)sum=0;
}
sum=0;
for(i=0;i<n;i++){
sum+=a[i];
minn=min(minn,sum);
if(sum>0)sum=0;
}
if(f==1)maxx=max(maxx,s-minn);
printf("%I64d\n",maxx);
}
return 0;
}
最新文章
- centos shell编程6一些工作中实践脚本 nagios监控脚本 自定义zabbix脚本 mysql备份脚本 zabbix错误日志 直接送给bc做计算 gzip innobackupex/Xtrabackup 第四十节课
- Java基础之访问文件与目录——创建目录(CreatingDirectories)
- (转)Eclipse “cannot be resolved to a type” error
- C# 通过线程来控制进度条(转)--讲解多线程对界面的操作
- Python快速教程
- Shell字符串使用十进制转换
- 配置并学习微信JS-SDK(2)—图片接口
- java 新手
- HBase 手动 flush 机制梳理
- C语言中sprintf()函数的用法
- Unity3D项目优化(转)
- OCR图片识别引擎
- UVa 573 - The Snail
- obj-c编程10:Foundation库中类的使用(6)[线程和操作队列]
- Ansa 自动加载用户脚本设置
- php7 三元运算 精简
- string部分方法
- LSTM如何解决梯度消失或爆炸的?
- Linux内核设计与实现 第十七章
- 什么是redis,redis简介