(基础dp(最大连续子串和))华中区邀请赛，B.Magic

Problem 1565 - B - Magic

Time Limit : 1000MS    Memory Limit : 65536KB   

Total Submit : 439   Accepted : 163   Special Judge : No

Description

Here are n numbers.

You have a magic : first , you choose a interval [l,r],and then each Si(l<=i<=r) will be ( 10 – Si ) % 10.

You can use the magic at most once to make sum of all the numbers to be maximum.

What is the maximum sum you can get?

Input

First line of each case contains a number n.(1 ≤  n ≤ 1 000 000).

Next line contains n numbers without space-separated. Each position corresponds to a number of 0-9.

Output

Output the answer on a single line for each case.

Sample Input

10
3775053808
10
2580294019
10
4701956095

Sample Output

50
50
54

/*
令Ti = (10 - Si) % 10 - Si, sum = Sigma(Si);
答案就是(sum + (T[]的最大连续子串和))。

DP求解“最大连续子串和”问题。
dp[i]:=以t[i]结尾的最大连续子串和。
则dp[i] = max(dp[i - 1] + t[i], t[i])。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
typedef long long LL;
const int INF = 0xfffffff;
char s[maxn];
int t[maxn];
int dp[maxn];
int main()
{
	//freopen("f:\\input.txt", "r", stdin);
	int n;
	while (~scanf("%d", &n))
	{
		scanf("%s", s);
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += s[i] - '0';
			t[i] = (10 - (s[i] - '0')) % 10 - (s[i] - '0');
		}

		int ret = max(0, t[0]);
		dp[0] = t[0];
		for (int i = 1; i < n; i++)
		{
			dp[i] = max(dp[i - 1] + t[i], t[i]);
			ret = max(ret, dp[i]);
		}
		printf("%d\n", sum + ret);
	}
	return 0;
}