day-58 最佳观光组合
思路
用right表示最佳观光组合的右边的景点的索引，同时维护一个该景点左边values[left]+left的最大值
解题过程
这样在遍历过程中，以right为右边景点的最佳得分即为values[right]-right+leftmax，再与ans比较，选择较大的那一个，同时维护leftmax的值，leftmax=Math.max(leftmax,values[right]+right)
Code
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int len=values.length;
int leftmax=0;
int ans=0;
for(int right=0;right<len;right++){
ans=Math.max(ans,values[right]-right+leftmax);
leftmax=Math.max(leftmax,values[right]+right);
}
return ans;
}
}
作者：菜卷
链接：https://leetcode.cn/problems/best-sightseeing-pair/solutions/2926968/zui-jia-guan-guang-zu-he-by-ashi-jian-ch-ey5l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。