题目简介:
给你一个正整数数组 values
,其中 values[i]
表示第 i
个观光景点的评分,并且两个景点 i
和 j
之间的 距离 为 j - i
。
一对景点(i < j
)组成的观光组合的得分为 values[i] + values[j] + i - j
,也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
解题方法:
用两个变量,ans,maxval分别记录最优路线和最优起点,每当循环遍历一次,那么最优起点的值应当减一(这是由于距离增加带来的起点的在组合中评分降低)。
时间复杂度为:O(n)
空间复杂度为:O(1)
public class question_1014 {
public static void main(String[] args) {
int[] arr = {8,1,5,2,6};
Solution_1014 solution1014= new Solution_1014();
System.out.println(solution1014.maxScoreSightseeingPair(arr));
}
}
class Solution_1014 {
public int maxScoreSightseeingPair(int[] values) {
int ans = 0;
int maxval = values[0] - 1;
for(int i = 1; i<values.length ;i++){
//记录评分较高观光组合
ans = Math.max(ans,values[i] + maxval);
//-1,每次循环距离加1,评分减一,maxval保存评分较高的景点
maxval = Math.max(maxval,values[i]) - 1;
}
return ans;
}
}
标签:int,观光,Solution,values,景点,1014,LeetCode
From: https://blog.csdn.net/2302_77430843/article/details/142448466