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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include "kanapka.h"
#include "message.h"

#include <algorithm>
#include <iostream>

using namespace std;
/*
	long long GetN(){
		//int[] arr = { -100, 10, -2, 5, -4, 3, -5, 1 };	
		return 7;
		//return 100000000ll;
	}
	
	long long GetTaste(long long i){
		long long arr[] = { 10, -2, 5, -4, 3, -5, 100 };	
		//return i * pow(-1, i);
		return arr[i];
	}
	
	int MyNodeId(){
		return 0;
	}
*/

	long long* fillFromStart() {
		long long* res = new long long[GetN()];
		res[0] = GetTaste(0);
		for (long long i = 1; i < GetN(); i++) {
			res[i] = res[i - 1] + GetTaste(i);
		}
		return res;
	}

	long long* fillFromEnd() {
		long long* res = new long long[GetN()];
		res[GetN() - 1] = GetTaste(GetN() - 1);
		for (long long i = GetN()- 2; i >= 0; i--) {
			res[i] = res[i + 1] + GetTaste(i);
		}
		return res;
	}
	
	long long getMaxFromArray(long long* arr, long start, long end) {
		if (end < 0 || start >= GetN()) {
			return 0;
		}
		long res = arr[start];
		for (int i = start + 1; i <= end; i++) {
			if (arr[i] > res) {
				res = arr[i];
			}
		}
		return res;
	}	
	
	long long getFirstIndexOfValueInArray(long long* arr, bool fromLeft, long long value){
		if(fromLeft){
			for (long long i = 0; i < GetN(); i++) {
				if(arr[i]==value){
					return i;
				}
			}
		}
		else{
			for (long long i = GetN()-1; i > 0; i--) {
				if(arr[i]==value){
					return i;
				}
			}
		}
		return -1;
	}

	long long getBestSum(long long* arr1, long long* arr2) {
		long long res1 = 0;
		long long res2 = 0;
		
		res1 = getMaxFromArray(arr1, 0, GetN()-1);
		res2 = getMaxFromArray(arr2, 0, GetN()-1);
		
		if(res1 < 0){
			return res2;
		}
		if(res2 < 0){
			return res1;
		}
		
		if(res1>=res2){
			res2 = getMaxFromArray(arr2, getFirstIndexOfValueInArray(arr1, true, res1)+1, GetN()-1);
		}
		else{
			res1 = getMaxFromArray(arr1, 0, getFirstIndexOfValueInArray(arr2, false, res1)-1);
		}
/*		
		for (long long i = -1; i < GetN(); i++) {
			res1 = getMaxFromArray(arr1, 0, i);
			res2 = getMaxFromArray(arr2, i + 1, GetN() - 1);
			if (res1 + res2 > res) {
				res = res1 + res2;
			}
		}
*/		
		return res1+res2;
	}

	void printArray(long long* arr) {
		for (long long i = 0; i < GetN(); i++) {
			cout<<arr[i]<<" ";			
		}
		cout<<endl;
	}

	int main() {
		if (MyNodeId() == 0) {
			long long N = GetN();
			if (N == 1){
				cout << max(0ll, GetTaste(0)) << endl;
			}
			else{
				//int[] arr = { -100, 10, -2, 5, -4, 3, -5, 1 };	
				long long* arr1 = fillFromStart();
				long long* arr2 = fillFromEnd();
				//printArray(arr1);
				//printArray(arr2);
				cout << max(0ll, getBestSum(arr1, arr2)) << endl;
			}
		}
	return 0;
	}