问题描述
给n个数{A}_{1},{A}_{2}....{A}_{n}A1,A2....An,你可以选择一个区间(也可以不选)，区间里每个数x变成f(x),其中f(x)=(1890x+143) mod 10007f(x)=(1890x+143)mod10007。问最后n个数之和最大可能为多少。
输入描述
输入有多组数据。
每组数据第一行包含一个整数n.(1\leq n\leq {10}^{5})(1≤n≤105)
第二行n个整数{A}_{1},{A}_{2}....{A}_{n}A1,A2....An.(0\leq {A}_{i}\leq {10}^{4})(0≤Ai≤104)
数据保证 \sum n\leq {10}^{6}∑n≤106.
输出描述
对于每组数据输出一行答案.
输入样例
2
10000 9999
5
1 9999 1 9999 1
输出样例
19999
22033
思路：
对于输入的每个数求出他们进行运算后的差值，然后求最大区域和即可
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
#define N 100050
int f[N];
int a[N];
int main()
{
int T,n;
while(scanf("%d",&n) != EOF)
{
int tsum = 0;
int sum = 0;
int tel = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d",&f[i]);
tsum += f[i];
int tt = (f[i]*1890+143)%10007-f[i];
if(sum + tt < 0)
{
tel = max(tel,sum);
sum = 0;
}
else
{
sum += tt;
if(sum > tel)
tel= sum;
}
}
if(tel > 0)
tsum += tel;
printf("%d\n",tsum);
}
}