字节青训Marscode11：观光景点组合得分问题

这道题的核心是通过计算每一对景点的组合得分，找到能获得最高得分的组合。具体来说，给定一个景点数组 values，我们需要找到两个景点 (i, j)，使得：

得分=values[i]+values[j]+i−j\text{得分} = values[i] + values[j] + i - j

其中，i < j，并且我们希望通过遍历所有可能的 (i, j) 对来找到得分最大的一对。

分析

组合得分的公式 values[i] + values[j] + i - j 中包含了：

• values[i] + values[j]：表示两个景点的评分之和。
• i - j：表示景点之间的距离，实际上是负数，因为 i < j。

为了获得更高的得分，我们可以将这个公式进行重新组织，得到：

得分=(values[i]+i)+(values[j]−j)\text{得分} = (values[i] + i) + (values[j] - j)

因此，可以通过以下步骤来简化问题：

1. 将每个景点的得分视为 values[i] + i，我们称之为 score_i。
2. 将每个景点的得分视为 values[j] - j，我们称之为 score_j。
3. 我们的目标是：最大化 score_i + score_j，其中 i < j。

解决方案：

我们可以通过遍历数组，记录每个位置的 score_i，然后计算当前 score_j 与之前的最大 score_i 的和，得到当前的最大得分。

实现：

#include <vector>
#include <iostream>
#include <algorithm>

int solution(std::vector<int> values) {
    int n = values.size();
    int max_score = INT_MIN;  // 初始化最大得分为最小整数
    int max_value = values[0] + 0;  // 第一个景点的得分是 values[0] + 0
    
    for (int j = 1; j < n; ++j) {
        // 计算当前景点的得分
        int score_j = values[j] - j;
        
        // 更新最大得分
        max_score = std::max(max_score, max_value + score_j);
        
        // 更新 max_value 为前一个景点的得分
        max_value = std::max(max_value, values[j] + j);
    }
    
    return max_score;
}

int main() {
    // 测试用例
    std::cout << (solution({8, 3, 5, 5, 6}) == 11) << std::endl;
    std::cout << (solution({10, 4, 8, 7}) == 16) << std::endl;
    std::cout << (solution({1, 2, 3, 4, 5}) == 8) << std::endl;
    return 0;
}

代码解释：

1. 初始化：

   • max_score 变量存储最大得分，初始为 INT_MIN。
   • max_value 变量存储到当前位置之前的最大得分，初始为 values[0] + 0。

2. 遍历景点：

   • 从第 1 个景点开始（索引 1），计算 score_j = values[j] - j。
   • 更新最大得分 max_score 为当前 max_value + score_j 和之前的最大得分中的较大值。
   • 更新 max_value 为 values[j] + j 和之前的 max_value 中的较大值。

3. 最终返回：

   • 最后返回 max_score 即为所求的最大得分。

测试用例：

• 输入 1：

  {8, 3, 5, 5, 6}
  

  • 计算得分的最大组合为景点 0 和景点 4，得分为 8 + 6 + 0 - 4 = 11。

• 输入 2：

  {10, 4, 8, 7}
  

  • 计算得分的最大组合为景点 0 和景点 2，得分为 10 + 8 + 0 - 2 = 16。

• 输入 3：

  {1, 2, 3, 4, 5}
  

  • 计算得分的最大组合为景点 0 和景点 4，得分为 1 + 5 + 0 - 4 = 8。

时间复杂度：

• 由于我们只遍历了一次景点数组，因此时间复杂度为 O(n)，其中 n 是景点的数量。

空间复杂度：

• 由于我们只使用了常数的额外空间，空间复杂度为 O(1)。

结论：

这种方法通过利用局部最大值优化了暴力解法，达到了线性时间复杂度，适用于大规模数据。