Best Sightseeing Pair

LeetCode Q 1014 - Best Sightseeing Pair

Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1: Input: [8,1,5,2,6] ; Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

Note:

• 2 <= A.length <= 50000
• 1 <= A[i] <= 1000

Solution :

We use a var max_i to track the maximum number until ith number in A. The maxinum Score could only happen between the local max num and some number. Say the maximum score happens only when using the local max num as the starting spot. This is kind of Greedy algorithm.

Code:

public int maxScoreSightseeingPair(int[] A) {
	
	int res = 0;

	for (int j = 1, max_i = A[0] - 1; j < A.length; j++, max_i--) {
		res = Math.max(res, A[j] + max_i);
		max_i = Math.max(max_i, A[j]);
	}

	return res;
}