# 1014. 最佳观光组合 ## 题目地址(1014. 最佳观光组合) <https://leetcode-cn.com/problems/best-sightseeing-pair/> ## 题目描述 ``` <pre class="calibre18">``` 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。 返回一对观光景点能取得的最高分。 示例： 输入：[8,1,5,2,6] 输出：11 解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11 提示： 2 <= A.length <= 50000 1 <= A[i] <= 1000 ``` ``` ## 前置知识 - 动态规划 ## 公司 - 阿里 - 字节 ## 思路 最简单的思路就是两两组合，找出最大的，妥妥超时，我们来看下代码： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i + <span class="hljs-params">1</span>, n): res = max(res, A[i] + A[j] + i - j) <span class="hljs-keyword">return</span> res ``` ``` 我们思考如何优化。 其实我们可以遍历一遍数组，对于数组的每一项`A[j] - j` 我们都去前面找`最大`的 A\[i\] + i （这样才能保证结果最大）。 我们考虑使用动态规划来解决, 我们使用 dp\[i\] 来表示 数组 A 前 i 项的`A[i] + i`的最大值。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) dp = [float(<span class="hljs-string">'-inf'</span>)] * (n + <span class="hljs-params">1</span>) res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): dp[i + <span class="hljs-params">1</span>] = max(dp[i], A[i] + i) res = max(res, dp[i] + A[i] - i) <span class="hljs-keyword">return</span> res ``` ``` 如上其实我们发现，dp\[i + 1\] 只和 dp\[i\] 有关，这是一个空间优化的信号。我们其实可以使用一个变量来记录，而不必要使用一个数组，代码见下方。 ## 关键点解析 - 空间换时间 - dp 空间优化 ## 代码 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) pre = A[<span class="hljs-params">0</span>] + <span class="hljs-params">0</span> res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): res = max(res, pre + A[i] - i) pre = max(pre, A[i] + i) <span class="hljs-keyword">return</span> res ``` ``` ## 小技巧 Python 的代码如果不使用 max，而是使用 if else 效率目测会更高，大家可以试一下。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) pre = A[<span class="hljs-params">0</span>] + <span class="hljs-params">0</span> res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): <span class="hljs-title"># res = max(res, pre + A[i] - i)</span> <span class="hljs-title"># pre = max(pre, A[i] + i)</span> res = res <span class="hljs-keyword">if</span> res > pre + A[i] - i <span class="hljs-keyword">else</span> pre + A[i] - i pre = pre <span class="hljs-keyword">if</span> pre > A[i] + i <span class="hljs-keyword">else</span> A[i] + i <span class="hljs-keyword">return</span> res ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。