力扣AC：最佳观光组合 - 解方程

题目链接

最佳观光组合

题目描述

实现代码

思路：首先把结果通过i和j的形式表达出来就是如下：

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

可以将其分成两个部分：

1. values[i] - i
2. values[j] + j

我们可以将其看成是两个变量的方程，这里假设将j看成是变量，进行循环，找到在j之前的 values[i] - i的最大值，同时也找到所有j中的values[j] + j的最大值，两者相加即为最终结果，只需要遍历一次，实现代码如下：

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0, mx = values[0] + 0;
        for (int j = 1; j < values.length; ++j) {
            ans = Math.max(ans, mx + values[j] - j);
            // 边遍历边维护
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }
}