11. 观光景点组合得分问题 |豆包MarsCode AI刷题

观光景点组合得分问题 - MarsCode

题目要求我们计算一组观光景点的最高组合得分。每个景点都有一个评分，保存在数组 values 中。一对景点 (i < j) 的观光组合得分为 values[i] + values[j] + i - j，即两者评分之和减去它们之间的距离。

我们需要找到一种方法，使得在所有可能的景点组合中，得分最高。

解题思路

理解公式：
- 组合得分公式为 values[i] + values[j] + i - j。
- 可以将其拆分为 (values[i] + i) + (values[j] - j)。
优化思路：
- 对于每个 j，我们只需要找到在 i < j 的情况下，使得 values[i] + i 最大的 i。
- 这样，我们可以通过一次遍历数组来计算每个 j 对应的最高得分。
算法步骤：
- 初始化一个变量 max_i_plus_value 来保存当前最大的 values[i] + i。
- 遍历数组 values，对于每个 j，计算 max_i_plus_value + values[j] - j，并更新最大得分。
- 同时更新 max_i_plus_value。

数据结构选择

使用一个变量 max_i_plus_value 来保存当前最大的 values[i] + i。
使用一个变量 max_score 来保存当前的最大得分。

复杂度分析

时间复杂度：O(n)，因为我们只需要遍历数组一次。
空间复杂度：O(1)，因为我们只使用了常数个额外变量。

通过上述思路，我们可以高效地找到最高得分。

#include <vector>
#include <iostream>
#include<cmath>int solution(std::vector<int> values) {// write code hereint mx = 0;for(int i = 0 ; i < values.size();i++){for(int j = i + 1;j < values.size();j++){mx = fmax(values[i] + values[j] + i - j,mx);}}return mx; // Placeholder return
}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;
}