力扣题解1014
大家好，欢迎来到无限大的频道。
今日继续给大家带来力扣题解。
题目描述（中等）：
最佳观光组合
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
题目分析：
我们需要找到一对景点（i < j），使得它们的观光组合得分最大。组合得分的计算方式是 values[i] + values[j] + i - j。这一公式可以拆分为 (values[i] + i) + (values[j] - j)。这样，我们的问题就可以转化为：在遍历到位置 j 时，找一个最优的 i 使得 (values[i] + i) 最大。
这样，我们可以通过线性扫描数组来完成任务。
解题思路：
-
初始化变量：我们需要两个变量：max_score 用来存储最大的得分，max_i 用来存储最大 values[i] + i。
-
遍历数组：从第二个元素（j = 1）开始遍历 values。
-
计算当前组合得分：对于每个 j，计算 current_score 为 max_i + values[j] - j。
-
更新最大得分：如果 current_score 大于 max_score，更新 max_score。
-
更新 max_i：在每一步，更新 max_i 为 max(max_i, values[j] + j)。这是为了保证后续位置 j 使用到最优的 i。
-
-
返回最大得分：最终返回 max_score。
参考代码如下：
int maxScoreSightseeingPair(int* values, int valuesSize) {// 初始化 max_i 为第一个元素的值加上它的索引int max_i = values[0] + 0;int max_score = 0;
// 从第二个元素开始遍历for (int j = 1; j < valuesSize; j++) {// 计算当前组合的得分int current_score = max_i + values[j] - j;// 更新最优得分if (current_score > max_score) {max_score = current_score;}// 更新 max_i，使其为当前元素的值加上它的索引，或者保持为之前的最大值if (values[j] + j > max_i) {max_i = values[j] + j;}}
return max_score;
}这个算法虽然没有显式地使用动态规划的传统形式（例如，使用表格存储子问题的解），但它确实利用了一种动态规划的思想来优化计算过程。让我们深入分析一下。
动态规划的基本思想
动态规划（Dynamic Programming, DP）通常用于解决可以分解为重叠子问题的优化问题。它的核心思想是通过保存已经计算过的结果来避免重复计算，从而提高效率。动态规划通常涉及以下几个步骤：
1. 定义状态：明确需要存储的信息。
2. 建立状态转移方程：确定如何从已知状态推导出新状态。
3. 初始化状态：设置初始条件。
4. 计算结果：根据状态转移方程计算最终结果。
在这个算法中的运用
在 `maxScoreSightseeingPair` 函数中，虽然没有使用表格来存储中间结果，但它通过以下方式实现了动态规划的思想：
1. 定义状态：
- `max_i` 代表在当前元素之前（即 `j` 的前一个元素）可以获得的最大得分 `values[i] + i`。这个状态在每一步中都在更新。
2. 状态转移：
- 在每次循环中，我们通过 `max_i` 来计算当前得分 `current_score`。这个得分依赖于之前的状态 `max_i` 和当前的 `values[j] - j`。这样，我们实际上在用 `max_i` 的值来动态计算出当前 `j` 的最优得分。
3. 初始化状态：
- `max_i` 初始为 `values[0] + 0`，这是我们在计算中需要的第一个状态。
4. 计算结果：
- 通过遍历整个数组，更新 `max_score` 和 `max_i`，最终得到最大得分。
虽然这个算法没有使用动态规划的典型方式（如二维数组或一维数组来存储多个状态），但它确实利用了动态规划的核心思想：通过维护一个状态（`max_i`），在遍历过程中动态更新并计算结果。
因此，可以说这个算法在某种程度上是基于动态规划的思想，但它的实现方式更为简洁，使用了常量级的空间来存储状态，而不是使用一个完整的 DP 表。
复杂度：
时间复杂度：
在代码中，我们只进行了一次遍历，遍历了整个数组 values。具体分析如下：
-
遍历数组：我们使用一个 for 循环从 j = 1 到 valuesSize - 1，这意味着循环的次数是 n-1，其中 n 是数组的长度。
-
每次迭代的操作：在循环体内，我们进行了一些常数时间的操作（如加法、比较、赋值等），这些操作的时间复杂度都是 O(1)。
因此，整个算法的时间复杂度为 O(n)，其中 n 是数组 values 的长度。
空间复杂度：
在空间复杂度方面：
-
使用的额外空间：我们只使用了几个额外的变量（max_i、max_score 和 current_score），这些变量占用的空间是常数级别的。
-
输入数组：我们没有使用任何额外的数据结构来存储数据，输入数组 values 在空间复杂度的计算中不被考虑。
因此，整个算法的空间复杂度为 O(1)，即只使用了常量级的额外空间。
总结
-
时间复杂度：O(n)
-
空间复杂度：O(1)