1014.best-sightseeing-pair.md

1014. Best Sightseeing Pair

Enumeration

The score of pair (i, j) is:

values[i] + values[j] + i - j

which can be rewritten as:

(values[i] + i) + (values[j] - j).

Idea!! This means we can keep track of the maximum value of values[i] + i seen so far as we iterate through the array, and for each j, we compute values[j] - j and update the answer.

fun maxScoreSightseeingPair(values: IntArray): Int {
    // We keep track of the maximum value of `values[i] + i]` seen so far
    var maxValueI = values.first()
    // The global maximum score
    var maxScore = maxValueI
    for (j in 1 until values.size) {
        // We compute values[j] - j
        val maxValueJ = values[j] - j
        // Update the global maximum score
        maxScore = maxOf(maxScore, maxValueI + maxValueJ)
        // Also update the maximum value of `values[i] + i]` seen so far
        maxValueI = maxOf(maxValueI, values[j] + j)
    }
    return maxScore
}

WA

This implementation is to track the maximum value of values[i] and i seen so far in the separate variables. The problem is that we update the values[i] and i only when values[i] is greater, however, we don't check if (values[i] + i) is greater than (values[j] + j). We might have smaller values[i] but larger values[i] + i from closer i..

Let's see an example:

// The WA implementation
index      0, 1, 2, 3
value      2, 1, 1, 5
----------------------
maxValueI  2  2  2  5
     maxI  0  0  0  3
      ans  2  2  2  4 // WA
                 ^ // We don't update here because `maxValueI > values[j]` now.

// The AC implementation, we track `values[i] + i` seen so far
index      0, 1, 2, 3
value      2, 1, 1, 5
----------------------
maxValueI  2  2  1  5
     maxI  0  0  2  3
      ans  2  2  3  5 // AC
                 ^ // We update if we see a better `values[i] + i` (smaller `values[i]` but larger `i` that makes `values[i] + i` larger)

fun maxScoreSightseeingPair(values: IntArray): Int {
    var maxValueI = values.first()
    var maxI = 0
    var ans = maxValueI + maxI
    for (j in 1 until values.size) {
        val valueJ = values[j]
        ans = maxOf(ans, maxValueI + maxI + valueJ - j)
        if (maxValueI <= valueJ) {
            maxValueI = valueJ
            maxI = j
        }
    }
    return ans
}