1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, maxSoFar = 0;
        for (int i = 0; i < values.length; i++) {
            ans = Math.max(ans, values[i] + maxSoFar);
            maxSoFar = Math.max(maxSoFar, values[i]) - 1;
        }
        return ans;
    }
}

可以这么想, 我们把values[i] + i - j合并在一起, i位置可以贡献的score就是values[i] + i - j, j位置贡献的score就是values[j]. 我们想要知道j之前的那个位置values[i] + i - j最大, 此时它和values[j]配对能得到最大的值. 如果我们往右移动一格到达j + 1, 毋庸置疑, [0, j - 1]位置能贡献的score都会减去1, 那么j处能贡献多少呢? values[j] + j - (j + 1) == values[j] - 1. 因此如果我们之前知道[0, j - 1]中最大的贡献值是多少, 我们让它和values[j]比较, 如果values[j]大, 那么我们就知道j + 1左侧最大贡献值就是在j处取到, 否则还是在之前的[0, j - 1]中最大贡献值的index处取到. 需要注意的是, 在得到哪个最大后, 要减去1, 因为我们已经到达了j + 1处.

这种想法可以认为数组的大小是活动的. 我们在j处时, [0, j]能贡献的值可以画成直方图. 如果我们移动j到j + 1, 那么[0, j]的贡献值就会集体减去1, 如果我们从j + 1移动到j, [0, j]的贡献值就会集体 + 1. 等于是动态的, 这样理解能够帮助我们了解这个逻辑的过程是什么样子的.

时间复杂度: O(n)
空间复杂度: O(1)

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, maxSoFar = 0;
        for (int i = 0; i < values.length; i++) {
            ans = Math.max(ans, values[i] - i + maxSoFar);
            maxSoFar = Math.max(maxSoFar, values[i] + i);
        }
        return ans;
    }
}

这个方法是把values[i] + i合在一起, values[j] - j合在一起, 那么这就变成在某个位置j, 我如果知道j之前最大的values[i] + i是多少就ok了. 这其实就是找最大值的过程了. 边走边更新遇到的最大的values[i] + i, 然后看此时的values[j] - j和之前的最大的values[i] + i能否比之前记录的最大ans还要大.

时间复杂度: O(N)
空间复杂度: O(N)