Maximum absolute subarrays

5

1 votes
Problem

You are given an array A consisting of n integers. Your task is to divide a subarray A[i,j] into two contiguous parts A[i,k] and A[k+1,j]. Here, any of these parts can be empty.

If S[i,j] denotes the sum of all elements of subarray A[i,j] (the sum of empty sub-array is zero), then X[i,j] denotes the maximum value of abs(S[i,k]S[k+1,j]) where i1kj and abs(Z) is the absolute value of Z.

Note: Sub-array A[i,j] is called empty if i>j

You are required to print the maximum value of X[i,j] where 1ijn.

Input format

  • First line: An integer n denoting the size of the array
  • Next lines: n space-separated integers denoting the elements of the array

Output format

Print an integer that denotes the maximum value of X[i,j]

Constraints

1n3×105

109A[i]109

Sample Input
10
-3 4 3 -5 7 -8 5 -5 3 8
Sample Output
19
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The maximum value X[i, j] can be obtained for i = 6 and j = 10.

Here if we take k = 8,we get

X[i, j] = abs(S[i, k] - S[k + 1, j])

        = abs(S[6, 8] - S[9, 10]) = abs[ (-8 + 5 - 5) - (3 + 8) ]

        = abs(-8 - 11) = abs(-19) = 19, which is maximum.

Editor Image

?