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

开启你的职业生涯

完成课程获得认证

开始学习