1014. Best Sightseeing Pair

MediumView on LeetCode

Array Dynamic Programming

Time: O(n)

Space: O(1)

Intuition

Maximize A[i]+A[j]+i-j = (A[i]+i) + (A[j]-j) for i<j. Track max (A[i]+i) scanning left to right.

Algorithm

1maxLeft = A[0]+0.
2For j from 1: ans = max(ans, maxLeft + A[j]-j). Then maxLeft = max(maxLeft, A[j]+j).

Common Pitfalls

•Update maxLeft AFTER computing answer to maintain i<j constraint.

1014.cs

// Approach: Single pass; track best previous score (value - index); for each position compute score and update the best previous by decrementing.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxScoreSightseeingPair(int[] values)
    {
        int ans = 0;
        int bestPrev = 0;

        foreach (var value in values)
        {
            ans = Math.Max(ans, value + bestPrev);
            bestPrev = Math.Max(bestPrev, value) - 1;
        }

        return ans;
    }
}

Was this solution helpful?