LeetCode.1014.最佳观光组合（中等）

题目

LeetCode.1014.最佳观光组合（中等）

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。、

题解

思路梳理

1. 对一个确定的j，需要在[0, j - 1]中选取一个i，使得观光组合得分最高。
2. 不知道选哪个j能让得分最高，就需要穷举所有j的取值可能性。

目标分析

目标是求最大的观察观光组合得分，那么就得思考得分与什么相关，能否分解为独立的几个部分，再穷举每个部分所有的可能性，看这些可能性是怎么操作得到的，就可以知道得分是怎么来的了。

具体分析

得分公式values[i] + values[j] + i - j里会变的东西就是i和j，这两个是独立变化的，那么就可以把公式拆成两部分：

1. 仅跟i相关的，即 values[i] + i，可以称为scoreI
2. 仅跟j相关的，即 values[j] - j，可以称为scoreJ

总分score = scoreI + scoreJ

对于一个确定的j，怎么使得得分最高呢？

1. j确定了， scoreJ 是确定的，不会变动。
2. 然后在[0, j - 1]中选取一个i，使得scoreI 最大，得分就是最高了。

不确定选哪个j可以得分最高，那就遍历数组，穷举j所有的取值可能。

但是按照这个思路，先穷举j，再在每个j处往回穷举i，时间复杂度是O($n^2$)，是否存在不必要的操作？

时间优化

仔细分析两个步骤可以发现，没有必要往回穷举i，因为i < j，在数组中遍历到j，j前面的位置肯定都遍历过了，i已经可以确定了；简单点说，j确定了，i就确定了。

class Solution {
    fun maxScoreSightseeingPair(values: IntArray): Int {
        val n = values.size
        if (n <= 1) return 0

        var maxScoreI = values[0] + 0
        var maxScore = 0
        
        // 穷举所有的j
        // 只有1个景点无法形成观光组合，所以从1开始遍历，这样至少2个有两个景点能形成观光组合
        for (j in 1 until n) {
            val scoreJ = values[j] - j
            val score = maxScoreI + scoreJ
            maxScore = maxOf(maxScore, score)
            
            // 上面已经处理过j，对于下一个j而言，需要知道下一个j前面最大的scoreI是多少
            val scoreI = values[j] + j
            maxScoreI = maxOf(maxScoreI, scoreI)
        }
        return maxScore
    }
}