Company: D. E. Shaw_Software developer_off-campus_3july
Difficulty: medium
Maximum Gross Value For an array arr of n integers, choose indices 1 <= i1 < i2 <= i3 <= n + 1 . Let sum(l, r) be the sum of the 1-based half-open interval arr[l..r) , which is zero when l = r . The gross value is sum(1, i1) - sum(i1, i2) + sum(i2, i3) - sum(i3, n + 1) . Print the maximum gross value over all valid triplets. Input Format The first line contains n . The second line contains n integers of arr . Output Format Print the maximum gross value. Constraints 1 <= n <= 3000 -10^9 <= arr[i] <= 10^9 Example Input: 4 -5 3 9 4 Output: 21 The triplet (1, 2, 5) gives 0 - (-5) + 16 - 0 = 21 .