1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<stdio.h>
#include<iostream>
#include<limits.h>
#include "kanapka.h"
#include "message.h"
using namespace std; 



int main()
{	
	long long n = GetN();

	
	long long leftMax[n]; 
	long long rightMax[n];
	long long leftMaxIndex[n];
	long long rightMaxIndex[n];
	
	long long sum = 0;
	long long max = LLONG_MIN; 
	long long maxIndex = -1;
	for(long long i = 0; i<n; ++i){
		sum+=GetTaste(i);
		if( sum > max){
			max = sum;
			maxIndex = i;
		}
		leftMax[i] = max;
		
//		cout << "LeftMax: " << i << " " << max << "\n";
		leftMaxIndex[i] = maxIndex;
	}
	
	sum = 0;
	max = LLONG_MIN;
	maxIndex = -1;
	for(long long i = n-1; i>=0; --i){
		sum+=GetTaste(i);
		if( sum > max){
			max = sum;
			maxIndex = i;
		}
		rightMax[i] = max;
//		cout << "RightMax: " << i << " " << max << "\n";
		rightMaxIndex[i] = maxIndex;
	}
	
	
	long long maxBalance = LLONG_MIN;
	for(long long firstRight = 0; firstRight<=n; ++firstRight){
		long long lastLeft = firstRight -1;
		long long rightAmount;
		long long leftAmount;
		if(firstRight > n-1) {
			rightAmount = 0;
		}else{
			rightAmount = rightMax[firstRight];
		}
		if(lastLeft < 0){
			leftAmount = 0;
		}else{
			leftAmount = leftMax[lastLeft];
		}
		long long balance = leftAmount + rightAmount;
		if(balance > maxBalance){
			maxBalance = balance;
		}
	}
	if(MyNodeId() == 0){
		cout << maxBalance;
	}
	
    return 0;
}