Best Sightseeing Pair

MediumKadane-style · Running Maximum🧩 Kadane's Running Best LeetCode #1014 ↗Updated Oct 30, 2026

Problem

Each spot i has an attractiveness values[i]. Visiting spots i < j scores values[i] + values[j] + i - j: their combined value minus the distance between them. Return the maximum score over all pairs.

Inputvalues = [8,1,5,2,6]Output11 (i=0, j=2: 8+5+0-2)

Inputvalues = [1,2]Output2

2 ≤ n ≤ 5·10⁴ · 1 ≤ values[i] ≤ 1000

Try it yourself

Java

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Split the score into a left part and a right part: (values[i] + i) + (values[j] - j). For each j we only need the best values[i] + i seen so far, which a single running maximum provides.

PatternKadane's Running Best

Instinct Best sum or product of a contiguous subarray in one pass? At each index choose - extend the run ending here or restart - and track the global best.

Memory hack Carry the bag only while it helps - a negative past is dead weight, drop it and restart here.

Open the Kadane's Running Best guide →

Approaches

Brute ForceTry Every Pair

Time O(n²)Space O(1)

Evaluate the formula for every pair i < j and keep the largest score. It follows the definition directly, so it is a reliable reference for testing.

Java

public int maxScoreSightseeingPair(int[] values) {
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < values.length; i++) {
        for (int j = i + 1; j < values.length; j++) {
            best = Math.max(best, values[i] + values[j] + i - j);
        }
    }
    return best;
}

About 1.25·10⁹ pairs at the limit — too slow.

BetterPrefix-Maximum Array

Time O(n)Space O(n)

Precompute leftBest[j] = max of values[i] + i over all i < j. Then each j scores leftBest[j] + values[j] - j, and we take the maximum — the separation of terms removes the inner loop.

Java

public int maxScoreSightseeingPair(int[] values) {
    int n = values.length;
    int[] leftBest = new int[n]; // leftBest[j] = max(values[i] + i) for i < j
    leftBest[1] = values[0];
    for (int j = 2; j < n; j++) {
        leftBest[j] = Math.max(leftBest[j - 1], values[j - 1] + j - 1);
    }
    int best = Integer.MIN_VALUE;
    for (int j = 1; j < n; j++) {
        best = Math.max(best, leftBest[j] + values[j] - j);
    }
    return best;
}

Linear time, but stores an extra array that is only read once per index.

OptimalSingle Pass with Running Max

Time O(n)Space O(1)

Fold the prefix array into one variable bestLeft. At each j, first score j as the right spot using bestLeft, then let j become a candidate left spot by updating bestLeft with values[j] + j.

Java

public int maxScoreSightseeingPair(int[] values) {
    int bestLeft = values[0]; // max of values[i] + i so far
    int best = Integer.MIN_VALUE;
    for (int j = 1; j < values.length; j++) {
        best = Math.max(best, bestLeft + values[j] - j); // j as the right spot
        bestLeft = Math.max(bestLeft, values[j] + j);    // j as a future left spot
    }
    return best;
}

Dry runvalues = [8,1,5,2,6]

j right spotL argmax of values[i]+i changed

start
8
L
1

5

2

6

bestLeft=8
j=1
8
L
1
j
5

2

6

8+1-1=8, best=8
j=2
8
L
1

5
j
2

6

8+5-2=11, best=11
j=3
8
L
1

5

2
j
6

8+2-3=7
j=4
8
L
1

5

2

6
j
8+6-4=10, ans 11 ✔

Same linear time with constant memory — the interview answer.

Pro tip

Score j before updating bestLeft — otherwise you may pair a spot with itself.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Pair	`O(n²)`	`O(1)`
Better	Prefix-Maximum Array	`O(n)`	`O(n)`
Optimal	Single Pass with Running Max	`O(n)`	`O(1)`

Common pitfalls

Updating bestLeft before scoring — allows i == j.
Tracking the max of values[i] alone — ignores the distance penalty.
Initialising the answer to 0 is fine here (scores ≥ 1), but MIN_VALUE is safer in general.

Interview tips

Rewrite the formula into an i-only part and a j-only part first.
Relate it to Best Time to Buy and Sell Stock: track the best “buy” so far.
Walk through the prefix-array version, then show it collapses to one variable.

Pattern

Running maximum (Kadane-style) → maximise f(i) + g(j) over i < j in one pass.

My notes saved in this browser