题干描述
给你一个正整数数组 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
题干分析
题干理解
给定一个正整数数组values，其中values[i]表示dii个观光景点的评分。两个景点i和j之间的距离为j-i。而一对景点组成的观光组合的得分计算公式为：score = values[i] + values[j] + i - j，也就是两个景点的评分之和减去它们之间的距离。本题的目标是找出一堆景点，使其得分最大，并返回这个最大得分。
解题思路
1.理解得分公式
已知原始的得分公式为：score = values[i] + values[j] + i - j，，将公式重新排列我们就得到了score = (values[i] + i) + (values[j] - j)，此时该公式可以划分为两个部分：
- (value[i] + i)：一个仅与i有关的值。
- (value[j] + j)：一个仅与j有关的值。
2.算法选择
暴力解法（过于麻烦，不可取）
- 枚举有有的（i，j）对，计算每个得分，时间复杂度为O(n^2),当大数组情况下效率低下。
线性解法（最后的选择）
- 在遍历数组是，维护当前位置之前的values[i] + i的最大值。
- 对于每个位置j（从第二个元素开始），计算当前得分
- 当设立最大得分以及当前得分，当当前得分大于当前的最大得分时，最大得分进行相关的更新，同时更新max_i为当前的values[j] + j，如果它更大，以便于在后面的计算中使用。
代码展示
int maxScoreSightseeingPair(int* values, int valuesSize){//1.初始化对打得分为0int max_score = 0;//2.初始化max_i为value[0] + 0,即第一个景点的评分加上其索引int max_i = values[0] + 0;//3.从第二个元素开始遍历数组for(int j = 0; j < valuesSize; j++){//计算当前的得分：之前的最大values[i] + i，加上当前values[j] - jint current_score = max_i + values[j] - j;//4.如果当前的得分大于当前的最大得分if(current_score > max_score){max_score = current_score;}//5.计算当前的values[j] + j,用于更新max_iint current_i = values[j] + j;//6.如果current_i大于max_i,更新max_iif(current_i > max_i){max_i = current_i;}}//7.返回最大得分return max_score;
}