Chương trình tìm tổng tối đa của dãy con, trong đó sự khác biệt của hai giá trị giống như sự khác biệt về vị trí của chúng trong Python

Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta chọn một dãy con gồm các giá trị tăng dần, trong đó sự khác biệt của mỗi số giống như sự khác biệt của hai chỉ số của chúng. Vì vậy, chúng ta phải tìm tổng lớn nhất của một dãy con như vậy.

Vì vậy, nếu đầu vào giống như nums =[6, 7, 9, 9, 8, 5], thì đầu ra sẽ là 22, khi chúng ta chọn dãy con [6, 7, 9] có chỉ số là [0, 1, 3]. Sự khác biệt giữa mỗi số liên tiếp là [1, 2] giống như sự khác biệt của các chỉ số của chúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• d:=một bản đồ trống

• đối với mỗi chỉ số i và giá trị x tính bằng nums, thực hiện

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

• trả về tối đa của tất cả các giá trị trong d

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví 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))

Đầu vào

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

Đầu ra

22