Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1706 Accepted Submission(s): 874
Problem Description
There is a number sequence A1,A2....An,you can select a interval [l,r] or not,all the numbers Ai(l≤i≤r) will become f.f.After that,the sum of n numbers should be as much as possible.What is the maximum sum?
Input
There are multiple test cases.
First line of each case contains a single integer n.(1≤n≤105)
Next line contains n integers A1,A2....An.(0≤Ai≤104)
It's guaranteed that ∑n≤106.
First line of each case contains a single integer n.(1≤n≤105)
Next line contains n integers A1,A2....An.(0≤Ai≤104)
It's guaranteed that ∑n≤106.
Output
For each test case,output the answer in a line.
Sample Input
2
10000 9999
5
1 9999 1 9999 1
Sample Output
19999
22033
Source
水题= =,有一种操作能把此数列中的某一段区间的数字全部变为f(xi),也可以不使用这个操作，求可获得的n个数的最大值。
我们不妨将f(xi)-xi处理出来表示变化值，从这个变化值数组中找到一段最大值就是能比SUMN(原始数列总和)最多增长多少，如果是一个负数按0处理表示不使用这个操作即可。好久没1A了尽管是水题还是>_<开森
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,M,i,j,k,t,a,b;
while(cin>>N){int s=0,maxn=0,sumn=0;
for(i=1;i<=N;++i){
cin>>a;
s+=a;
b=(1890*a+143)%10007-a;
sumn+=b;
if(sumn>maxn) maxn=sumn;
if(sumn<0) sumn=0;
}
cout<<s+maxn<<endl;
}
return 0;
}
using namespace std;
int main()
{
int N,M,i,j,k,t,a,b;
while(cin>>N){int s=0,maxn=0,sumn=0;
for(i=1;i<=N;++i){
cin>>a;
s+=a;
b=(1890*a+143)%10007-a;
sumn+=b;
if(sumn>maxn) maxn=sumn;
if(sumn<0) sumn=0;
}
cout<<s+maxn<<endl;
}
return 0;
}