第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
1014. 最佳观光组合

题目地址(1014. 最佳观光组合)

题目描述

1
给定正整数数组 A,A[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的距离为 j - i。
2
3
一对景点(i < j)组成的观光组合的得分为(A[i] + A[j] + i - j):景点的评分之和减去它们两者之间的距离。
4
5
返回一对观光景点能取得的最高分。
6
7
示例:
8
9
输入:[8,1,5,2,6]
10
输出:11
11
解释:i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
12
13
提示:
14
15
2 <= A.length <= 50000
16
1 <= A[i] <= 1000
Copied!

前置知识

  • 动态规划

公司

  • 阿里
  • 字节

思路

最简单的思路就是两两组合,找出最大的,妥妥超时,我们来看下代码:
1
class Solution:
2
def maxScoreSightseeingPair(self, A: List[int]) -> int:
3
n = len(A)
4
res = 0
5
for i in range(n - 1):
6
for j in range(i + 1, n):
7
res = max(res, A[i] + A[j] + i - j)
8
return res
Copied!
我们思考如何优化。 其实我们可以遍历一遍数组,对于数组的每一项A[j] - j 我们都去前面找最大的 A[i] + i (这样才能保证结果最大)。
我们考虑使用动态规划来解决, 我们使用 dp[i] 来表示 数组 A 前 i 项的A[i] + i的最大值。
1
class Solution:
2
def maxScoreSightseeingPair(self, A: List[int]) -> int:
3
n = len(A)
4
dp = [float('-inf')] * (n + 1)
5
res = 0
6
for i in range(n):
7
dp[i + 1] = max(dp[i], A[i] + i)
8
res = max(res, dp[i] + A[i] - i)
9
return res
Copied!
如上其实我们发现,dp[i + 1] 只和 dp[i] 有关,这是一个空间优化的信号。我们其实可以使用一个变量来记录,而不必要使用一个数组,代码见下方。

关键点解析

  • 空间换时间
  • dp 空间优化

代码

1
class Solution:
2
def maxScoreSightseeingPair(self, A: List[int]) -> int:
3
n = len(A)
4
pre = A[0] + 0
5
res = 0
6
for i in range(1, n):
7
res = max(res, pre + A[i] - i)
8
pre = max(pre, A[i] + i)
9
return res
Copied!

小技巧

Python 的代码如果不使用 max,而是使用 if else 效率目测会更高,大家可以试一下。
1
class Solution:
2
def maxScoreSightseeingPair(self, A: List[int]) -> int:
3
n = len(A)
4
pre = A[0] + 0
5
res = 0
6
for i in range(1, n):
7
# res = max(res, pre + A[i] - i)
8
# pre = max(pre, A[i] + i)
9
res = res if res > pre + A[i] - i else pre + A[i] - i
10
pre = pre if pre > A[i] + i else A[i] + i
11
return res
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。