当前位置：首页 > article >正文

day-58 最佳观光组合

article 2024/11/14 3:49:01

在这里插入图片描述
思路
用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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。