Python程式：查詢子序列的最大和，其中兩個值的差值與其在序列中的位置差值相同

假設我們有一個名為nums的數字列表，我們選擇一個嚴格遞增值的子序列，其中每個兩個數字的差值與其兩個索引的差值相同。因此，我們必須找到此類子序列的最大和。

因此，如果輸入類似於nums = [6, 7, 9, 9, 8, 5]，則輸出將為22，因為我們選擇子序列[6, 7, 9]，其索引為[0, 1, 3]。每個連續數字之間的差值為[1, 2]，與它們的索引差值相同。

為了解決這個問題，我們將遵循以下步驟：

• d := 一個空字典

• 對於nums中的每個索引i和值x，執行：

  • d[x − i] := d[x − i] + x

• 返回d中所有值的最大值

讓我們看看下面的實現來更好地理解：

示例

 線上演示

class Solution:
   def solve(self, nums):
      from collections import defaultdict
      d = defaultdict(int)
      for i, x in enumerate(nums):
         d[x − i] += x
      return max(d.values())

ob1 = Solution()
nums = [6, 7, 9, 9, 8, 5]
print(ob1.solve(nums))

輸入

[6, 7, 9, 9, 8, 5]

輸出

22

Arnab Chakraborty

更新於：2020年10月21日

瀏覽量：132

開啟你的職業生涯

完成課程獲得認證

開始學習