LeetCode题解1014.best-sightseeing-pair

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

https://leetcode-cn.com/problems/best-sightseeing-pair/description/

题目描述

给定正整数数组  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

思路

最简单的思路就是两两组合，找出最大的，妥妥超时，我们来看下代码：

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        res = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                res = max(res, A[i] + A[j] + i - j)
        return res

我们思考如何优化。 其实我们可以遍历一遍数组，对于数组的每一项A[j] - j 我们都去前面找最大的 A[i] + i （这样才能保证结果最大）。

我们考虑使用动态规划来解决, 我们使用 dp[i] 来表示 数组 A 前 i 项的A[i] + i的最大值。

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        dp = [float('-inf')] * (n + 1)
        res = 0
        for i in range(n):
            dp[i + 1] = max(dp[i], A[i] + i)
            res = max(res, dp[i] + A[i] - i)
        return res

如上其实我们发现，dp[i + 1] 只和 dp[i] 有关，这是一个空间优化的信号。我们其实可以使用一个变量来记录，而不必要使用一个数组，代码见下方。

关键点解析

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

代码

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        pre = A[0] + 0
        res = 0
        for i in range(1, n):
            res = max(res, pre + A[i] - i)
            pre = max(pre, A[i] + i)
        return res

小技巧

Python 的代码如果不使用 max，而是使用 if else 效率目测会更高，大家可以试一下。

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        n = len(A)
        pre = A[0] + 0
        res = 0
        for i in range(1, n):
            # res = max(res, pre + A[i] - i)
            # pre = max(pre, A[i] + i)
            res = res if res > pre + A[i] - i else pre + A[i] - i
            pre = pre if pre > A[i] + i else A[i] + i
        return res

可以在没有操作系统的情况下运行Java程序吗？ - java

我知道所有Java程序都由JVM执行。这使Java与所有操作系统兼容（一次编写，可在任何地方运行）。但是我可以在没有操作系统的情况下运行Java程序吗？也许只运行JVM？并且，如果可能，功能是否会受到任何影响？注意：我的主要问题是，java程序可以直接在硬件上运行（通过JVM）吗？我可以在计算机中“启动”任何低级别的JVM吗？ java大神给出的解决方案 实…

查看抽象类的方法是否未被扩展类之一覆盖的方法 - java

我有一个抽象类，比如AbstractClass和扩展该抽象类的多个其他类（700多个）。 AbstractClass有一个方法，比方说baseMethod()，它不是抽象方法。许多类（500+）覆盖该方法并具有自己的实现。现在，通过eclipse，我可以很容易地看到通过Ctrl+Shift+G覆盖该方法的方法，但是除了手动以外，还有其他方法可以看到不覆盖该方…

USB设备发行 - python

我目前正在使用PyUSB。由于我不熟悉USB，所以我不知道如何执行以下操作。我已经从Python PyUSB成功连接到我的USB设备硬件。在代码中，我需要重置USB设备硬件。通过向硬件发送命令来完成。现在，在硬件重置后，我想从Python PyUSB释放当前的USB设备。然后，我想在重置后将其重新连接到USB设备硬件。请让我知道，如何释放USB设备连接和接口…

使用Java检测用户计算机上是否安装了某些软件 - java

我有一个Java应用程序，它需要某些软件（其中一个是Perl）才能运行。我用来检测Perl的方法是：Runtime.getRuntime().exec("perl Test.pl"); 如果存在IOException，则声明不存在Perl。但是，我的一位用户抱怨该应用程序不断失败，因为他没有将Perl放在其路径变量中。所以这就是为什么我要…

如何修改休眠的SQL查询？ - java

我有点好奇，有没有办法修改hibernate的核心，以便我可以自定义生成的SQL query。例如，在生成的查询中添加功能以使用connect by prior（oracle）或我要自定义的任何其他子句。 java大神给出的解决方案 起初，这样的问题总是在我心中敲响警钟。你被警告了...AFAIK，hibernate使用所谓的dialects进行特定的优化。…