Given an array arr of n integers, for a triplet of 1-based indices i[1], i[2], i[3] (1 <= i[1] <= i[2] <= i[3] <= n + 1),
grossValue(i[1], i[2], i[3]) = sum[1, i[1]) - sum[i[1], i[2]) + sum[i[2], i[3]) - sum[i[3], n + 1)
Here, sum[l, r) (1 <= l <= r <= n + 1) uses half-open interval notation. It means that the interval includes index l but is exclusive of index r. In the special case where l = r, sum[l, r) is 0, and arr[l, r) is empty.
Find the maximum gross value of any valid triplet.
4 -5 3 9 4
21
arr = [-5, 3, 9, 4]. For triplet i[1] = 1, i[2] = 2, i[3] = 5:
- sum[1, 1) = 0
- sum[1, 2) = -5
- sum[2, 5) = 3 + 9 + 4 = 16
- sum[5, 5) = 0
grossValue = 0 - (-5) + 16 - 0 = 21 (maximum possible).
4 -1 1 -2 -2
6
Optimal indices yield gross value 6.
1. Let P[k] be the prefix sum of arr up to index k (with P[0] = 0). 2. Using 1-based indices a = i[1]-1, b = i[2]-1, c = i[3]-1 where 0 <= a <= b <= c <= n: grossValue = P[a] - (P[b] - P[a]) + (P[c] - P[b]) - (P[n] - P[c]) = 2 * (P[a] - P[b] + P[c]) - P[n] 3. To maximize grossValue, we maximize (P[a] - P[b] + P[c]) over 0 <= a <= b <= c <= n. 4. Precompute `max_c[b] = max_{b <= c <= n} P[c]` using a backward pass. 5. Iterate b from 0 to n while maintaining `max_a = max_{0 <= a <= b} P[a]`. Compute `candidate = max_a - P[b] + max_c[b]` and take the overall maximum. 6. Return `2 * best_candidate - P[n]` in O(N) time and O(N) space.