AlgoPressAppearance
1014-最佳观光组合
https://leetcode.cn/problems/best-sightseeing-pair
给你一个正整数数组 values，其中 values[i]表示第 i 个观光景点的评分，并且两个景点i 和j之间的 距离 为j - i。 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。 返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入：values = [1,2]
输出：2
提示： $$ 2 <= values.length <= 5 * 10^4 1 <= values[i] <= 1000 $$
解题思路1 双指针直接计算【会超时】
csharp
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int maxScore = 0;
for(int i=0; i<values.Length-1;i++){
for(int j=i+1;j<values.Length;j++){
int score = values[i] + values[j] + i - j;
maxScore = Math.Max(maxScore,score);
}
}
return maxScore;
}
}
解题思路2 ：动态规划 【ME】
注意本题的状态转移方程
我们首先初始化 dp 表示到达当前观光组合的最高分
dp[0] = values[0] 只有一个景点的时候，就是当前的值
dp[1] = values[1]+values[0]+0-1 当可以去第二个景点的时候，可以用题目公式算出最高分
max = max(dp[0],dp[1])
下面进入循环，到达 dp[i] 后有两种情况
一种是： 直接从i-1点过来 values[i] + values[i-1] - 1
另一种是：从i-1前某个点直接走过来，那么他的最高值应该是他不去它前面的那个点，扣除他前面那个点的值并且加上当前的值， 再-1步
然后步数多了一步 dp[i-1] - values[i-1] + values[i] - 1;
这两种情况取最大值，然后更新到全局的最大值中去
csharp
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int[] dp = new int[values.Length];
dp[0] = values[0];
dp[1] = values[1] + values[0] + 0 - 1;
int max = Math.Max(dp[0],dp[1]);
for(int i=2; i<values.Length; i++){
dp[i] = Math.Max(values[i] + values[i-1] - 1, dp[i-1] - values[i-1] + values[i] - 1);
max = Math.Max(max,dp[i]);
}
return max;
}
}
解题思路3： 官方解法 边遍历边维护 mx
这里是对解题思路1的优化，因为 O(n^2)不能通过所有测试用例，会超时 我们分析公式: score = values[i] + values[j] + i - j; 转化为
(values[i] + i) + (values[j] - j)
等于在遍历到j的时候，我们需要一个前置的 values[i]+i为最大的值来计算，那么我们在最开始循环的时候，就把这个值缓存起来，并且一直更新为最大的值 那么就只需要遍历数组一次就可以了，算法时间复杂度降低到 O(n)
csharp
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int score = 0, mx = values[0] + 0;
for (int j = 1; j < values.Length; ++j) {
score = Math.Max(score, mx + values[j] - j);
// 边遍历边维护
mx = Math.Max(mx, values[j] + j);
}
return score;
}
}
复习： 20220520
根据公式 values[i] + values[j] + i - j 转换为 (values[i] + i) + (values[j] - j)
比如 ： [8,1,5,2,6] ，当我们循环到 5 的时候，其实是找前面最大的 values[i]+i 的组合来计算就可以了，小的不用考虑。
csharp
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int max = 0;
int result = 0;
max = values[0] + 0;
for(int i=1; i<values.Length; i++){
result = Math.Max(result,max + values[i] - i);
max = Math.Max(max,values[i] + i);
}
return result;
}
}
复习:20220622
csharp
public class Solution {
public int MaxScoreSightseeingPair(int[] values) {
int max = 0;
int score = 0;
for(int i=0; i<values.Length; i++){
score = Math.Max(score, max+values[i]-i);
max = Math.Max(max,values[i]+i);
}
return score;
}
}