Leetcode 1014. Best Sightseeing Pair

Problem statement

https://leetcode.com/problems/best-sightseeing-pair/

Solution

Let us fix j, then we need to find A[j] - j + max_{i < j}(A[i] + i). So, it is enough to keep cumulative maximum for A[i] + i values.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maxScoreSightseeingPair(self, A):
        acc = [0] + list(accumulate([i+a for i, a in enumerate(A)], max))
        return max(A[j] - j + acc[j] for j in range(len(A)))