BinarySearch 0455 Distance Pair

Problem statement

https://binarysearch.com/problems/Distance-Pair/

Solution

Let B[i] = A[i] + i and C[j] = A[j] - j. Then if we evaluate cumulative max of prefixex of B and suffixes of C then we need to find maximum among pairs of corresponding elements.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        B = [a + i for i, a in enumerate(A)]
        C = [a - j for j, a in enumerate(A)]
        B_acc = [-float("inf")] + list(accumulate(B, max))
        C_acc = list(accumulate(C[::-1], max))[::-1] + [-float("inf")]
        return max(x + y for x, y in zip(B_acc, C_acc))