HDU 5586 Sum

Problem Description

There is a number sequence ,you can select a interval [l,r] or not,all the numbers  will become ..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. Next line contains n integers . It's guaranteed that .

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

求个 差值然后求个连续和最大就好了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
int n;
long long a[maxn], b[maxn], c[maxn], sum, k;

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        k = sum = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            b[i] = (a[i] * 1890 + 143) % 10007;
            c[i] = b[i] - a[i];
            sum += a[i];
        }
        long long u = 0;
        for (int i = 1; i <= n; i++)
        {
            if (u + c[i] > 0) u = u + c[i]; else u = 0;
            if (u > k) k = u;
        }
        printf("%I64d\n", sum + k);
    }
    return 0;
}