Problem Description

There is a number sequence A1,A2....An

,A1,A2....An

,A1,A2....An

,A1,A2....An

,A1,A2....An

,A1,A2....An

,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

 

Sample Output

 

Source

 

传送门 http://acm.hdu.edu.cn/showproblem.php?pid=5586

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n;

int bac(int s)

{

    return (1890*s+143)%10007;

}

int b[100005],a[100005];

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        memset(b,0,sizeof(b));

        memset(a,0,sizeof(a));

        int re=0;

        for(int i=0;i<n;i++)

            {

                scanf("%d",&a[i]);

                re=re+a[i];

                b[i]=bac(a[i])-a[i];

            }

          //  int exm=0;

            int maxn=0;

          for(int i=1;i<n;i++)

          {

              if(b[i]+b[i-1]>b[i])

                b[i]=b[i]+b[i-1];

       if(b[i]>maxn)

                     maxn=b[i];

          }

        printf("%d\n",re+maxn);

    }

    return 0;

}