Indian National Olympiad in Informatics 2015
In this problem you are given two lists of N integers, a1, a2, ..., aN and b1, b2, ... bN. For any pair (i, j) with i, j ϵ {1, 2, ..., N} we define the segment from i to j, written as [i, j], to be i, i + 1, ..., j if i ≤ j and i, i + 1, ..., N, 1, 2, ...,j if i > j. Thus if N = 5 then the [2, 4] = {2, 3, 4} and [4, 2] = {4, 5, 1, 2}.
With each segment [i, j] we associate a special sum SSum[i, j] as follows:
- SSum[i, i] = ai.
- If i ≠ j then, 
The positions i and j contribute ai and aj, respectively, to the sum while every other position k in [i, j] contributes bk.
Suppose N = 5 and that the two given sequences are as follows:
i
1
2
3
4
5
ai
2
3
2
3
1
bi
3
4
4
6
3
Then, SSum[1, 1] = 2, SSum[2, 4] = 3 + 4 + 3 = 10 and SSum[4, 2] = 3 + 3 + 3 + 3 = 12. Your aim is to compute the maximum value of SSum[i, j] over all segments [i, j]. In this example you can verify that this value is 18 (SSum[2, 1] = 18).
-----Input format-----
- The first line contains a single positive integer N.
- This is followed by a line containing N integers giving the values of the ais and this is followed by a line containing N integers giving the values of the bis.
-----Output format-----
A single integer in a single line giving the maximum possible special segment sum.
Note: The final value may not fit in a 32 bit integer. Use variables of an appropriate type to store and manipulate this value (long long in C/C++, long in Java).
-----Test Data-----
You may assume that -109 ≤ ai, bi ≤ 109.
Subtask 1 (10 Marks) 1 ≤ N ≤ 3000.
Subtask 2 (20 Marks) 1 ≤ N ≤ 106 and ai = bi for all 1 ≤ i ≤ N.
Subtask 3 (30 Marks) 3 ≤ N ≤106. Further a1 = b1 = aN = bN = -109 and for each
1 < k < N we have -999 ≤ ak, bk ≤ 999.
Subtask 4 (40 Marks) 1 ≤ N ≤ 106.
-----Example-----
Here is the sample input and output corresponding to the example above:
-----Sample input-----
5
2 3 2 3 1
3 4 4 6 3
-----Sample output-----
18
Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = [0]*100006
maximum = 0
prev= [0]*100006
diff= [0]*100006
summ = [0]*100006
prev[0] = b[0]
for i in a:
    maximum = max(maximum,i)
for j in range(n):
    prev[j] = b[j] +prev[j-1]
diff[0] = a[0] -prev[0]
summ[0] = a[0]
for i in range(1,n):
    diff[i] = max(diff[i-1],a[i]-prev[i])
for i in range(1,n):
    summ[i] = max(summ[i-1],a[i]+prev[i-1])
for i in range(1,n):
    maximum = max(maximum,a[i] + prev[i-1] + diff[i-1])
for i in range(1,n):
    maximum = max(maximum,a[i] +prev[n-1] -prev[i] +summ[i-1])
print(maximum)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = [0]*100006
maximum = 0
prev= [0]*100006
diff= [0]*100006
summ = [0]*100006
prev[0] = b[0]
for i in a:
    maximum = max(maximum,i)
for j in range(n):
    prev[j] = b[j] +prev[j-1]
diff[0] = a[0] -prev[0]
summ[0] = a[0]
for i in range(1,n):
    diff[i] = max(diff[i-1],a[i]-prev[i])
for i in range(1,n):
    summ[i] = max(summ[i-1],a[i]+prev[i-1])
for i in range(1,n):
    maximum = max(maximum,a[i] + prev[i-1] + diff[i-1])
for i in range(1,n):
    maximum = max(maximum,a[i] +prev[n-1] -prev[i] +summ[i-1])
print(maximum)