LeetCode 1014. 最佳觀光組合 | Python

文章目錄

• • • 1014. 最佳觀光組合
    • • 題目
      • 解題思路
      • 代碼實作
      • 實作結果
      • 總結

1014. 最佳觀光組合

題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/best-sightseeing-pair

題目

給定正整數數組 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

解題思路

我們審題後發現，其實題目的答案已經在題目中有所展現。【一對景點（i < j）組成的觀光組合的得分為（A[i] + A[j] + i - j）：景點的評分之和減去它們兩者之間的距離】，在這裡，我們可以發現套用上面的公式，周遊比較求出最大即可。

那麼我們使用暴力解的時候，代碼大緻如下：

def maxScoreSightseeingPair(self, A: List[int]) -> int:
    length = len(A)
    max_score = 0
    for i in range(length):
        for j in range(i+1, length):
            score = A[i] + A[j] + i - j
            if score > max_score:
                max_score = score
    return max_score
           

但是這裡無法通過所有的用例（執行結果：逾時）。

雖然執行之後會逾時，但是，這個思路的方向是沒有錯的。我們仔細看題目中所給的公式：

我們将其轉變為：

這樣比較容易能夠看出，可以将公式拆成兩個部分

A[i] + i

和

A[j] - j

。

當對數組開始周遊時，對于

A[j]

來說，這個值是固定的，

A[j]

對應的索引

j

也是固定的。是以

A[j]-j

這個值也是固定的。

現在要求

A[i] + i + A[j] - j, (i<j)

，對于

A[j]

而言，要使得結果最大，也就是求

A[i]+i

取得最大值的時候。

最終在所有的

A[j]

中取得最大的那個結果傳回。

具體的代碼實作如下。

代碼實作

class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        length = len(A)
        # 将公式轉變為 A[i] + i + A[j] - j, (i<j)
        # 拆分為 A[i] + i，A[j] - j
        # A[i] + i 初始化為 A[0] + 0
        max_value = A[0] + 0
        ans = 0
        for j in range(1, length):
            # 維護更新最大值
            # 這裡需要注意 i < j
            ans = max(ans, max_value + A[j] - j)
            # 這裡維護更新 A[i] + i 的值，這裡等同于與 A[i-1] + (i-1) 進行比較
            # max_value 初始化為 A[0] + 0，此時 i = j = 1
            max_value = max(max_value, A[j] + j)

        return ans
           

實作結果

總結

• 根據題意，可以先使用暴力解嘗試解決問題。這裡雖然會逾時，但可以确定方向是對的。
• 将題目中所給的公式進行轉換得到：

  A[i] + i + A[j] - j, (i<j)

  ，這裡需要注意

  i<j

  ；
• 對于

  A[j]

  而言這裡可以固定

  A[j]-j

  ，那麼公式求最大值，也即是求

  A[i]+i

  最大；
• 最終在所有的

  A[j]

  中挑選最大的結果傳回。

文章原創，如果覺得寫得好，歡迎點贊關注。微信公衆号《書所集錄》同步更新，同樣歡迎關注點贊。