1021. 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:

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

 

Thoughts:

Scan from left to right, record:

  • best score so far()
  • the best left element which could generate the largest score with the next element.
    • As we move on to the next, gap ++, impact/score — with the prev. best left element

 

class Solution {

    /**
     * @param Integer[] $A
     * @return Integer
     */
    function maxScoreSightseeingPair($A) {
        $bestResult = 0;    // Best Score (A[i] + A[j] + i - j)
        $bestAI = 0;        // The best choice of A[i] so far
        foreach($A as $a){
            // Moved to next, gap++, then the "sightseeing value" --
            $bestAI --; 
            // Best result = 
            $bestResult = max($bestResult, $bestAI + $a );
            $bestAI = max($a, $bestAI);
        }
        return $bestResult;
    }
}

well sure I can combine $bestAI –; into other expressions. Just to make it clear in this way.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.