| 50|[Pow(x, n)][050]| Math, Binary Search|

| 56|[Merge Intervals][056]| Array, Sort|

| 554|[Brick Wall][554]| Hash Table|

| 1014|[最佳观光组合][1014]| 数组|

[050]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/050/README.md

[056]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/056/README.md

[554]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md

[1014]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/1014/README.md

[004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md

[010]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/010/README.md

给定正整数数组`A`，`A[i]` 表示第`i` 个观光景点的评分，并且两个景点`i` 和`j` 之间的距离为`j - i`。

一对景点（`i < j`）组成的观光组合的得分为（`A[i] + A[j] + i - j`）：景点的评分之和**减去**它们两者之间的距离。

返回一对观光景点能取得的最高分。

**示例：**

**提示：**

**标签：** 数组

直接暴力两层 for 循环肯定过不了关，我们把公式变化为`(A[i] + i) + (A[j] - j)`，看到此应该就可以想到在每次遍历`j` 时，只需要知道`max(A[i] + i)` 即可。

classSolution {

publicintmaxScoreSightseeingPair(int[]A) {

int ans=0, cur=A[0]+0;

for (int j=1; j<A.length; j++) {

ans=Math.max(ans, cur+A[j]- j);// 计算当前最大得分

cur=Math.max(cur,A[j]+ j);// 更新最大的 A[i] + i

}

return ans;

}

publicstaticvoidmain(String[]args) {

Solution solution=newSolution();

int[]A=newint[]{8,1,5,2,6};

System.out.println(solution.maxScoreSightseeingPair(A));

}

}

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]

[title]:https://leetcode-cn.com/problems/best-sightseeing-pair/

[ajl]:https://github.com/Blankj/awesome-java-leetcode

packagecom.blankj.medium._1014;

publicclassSolution {

publicintmaxScoreSightseeingPair(int[]A) {

intans =0,cur =A[0] +0;

for (intj =1;j <A.length;j++) {

ans =Math.max(ans,cur +A[j] -j);// 计算当前最大得分

cur =Math.max(cur,A[j] +j);// 更新最大的 A[i] + i

}

returnans;

}

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

int[]A =newint[]{8,1,5,2,6};

System.out.println(solution.maxScoreSightseeingPair(A));

}

}