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 <= 500001 <= 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.