Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 287    Accepted Submission(s): 177

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(Ai).f(x)=(1890x+143)mod10007.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.

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

BestCoder Round #64 (div.2)

题目大意：

给n个数{A}_{1},{A}_{2}....{A}_{n}A​1​​,A​2​​....A​n​​,你可以选择一个区间(也可以不选)，区间里每个数x变成f(x),其中f(x)=(1890x+143) mod 10007f(x)=(1890x+143)mod10007。问最后n个数之和最大可能为多少。

解题思路：

就是比较一下大小就行了，但是是减去arr[i]的值。。。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e5+5;
const int mod = 1e4+7;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
LL gcd(LL a, LL b)
{
    if(b == 0)
        return a;
    return gcd(b, a%b);
}
int arr[maxn], data[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        LL sum = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&arr[i]);
            sum += arr[i];
            data[i] = ((arr[i]*1890+143)%mod) - arr[i];
        }
        LL Max = 0, tmp = 0;
        for(int i=0; i<n; i++)
        {
            tmp += data[i];
            if(tmp > Max)
                Max = tmp;
            if(tmp < 0)
                tmp = 0;
        }
        LL ret = sum+Max;
        printf("%I64d\n",ret);
    }
    return 0;
}