题目链接
题目描述
实现代码
思路:首先把结果通过i和j的形式表达出来就是如下:
values[i] + values[j] + j - i
可以将其分成两个部分:
- values[i] - i
- 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;
}
}