สมมติว่าเรามีรายการของตัวเลขที่เรียกว่า nums เราเลือกค่าที่ตามมาของค่าที่เพิ่มขึ้นอย่างเคร่งครัด โดยที่ผลต่างของตัวเลขแต่ละตัวจะเหมือนกับผลต่างของดัชนีทั้งสองตัว ดังนั้นเราต้องหาผลรวมสูงสุดของลำดับย่อยดังกล่าว
ดังนั้น หากอินพุตเท่ากับ nums =[6, 7, 9, 9, 8, 5] ผลลัพธ์จะเป็น 22 ขณะที่เราเลือกลำดับย่อย [6, 7, 9] ซึ่งมีดัชนีเป็น [0, 1, 3]. ความแตกต่างระหว่างตัวเลขแต่ละตัวเรียงกันคือ [1, 2] ซึ่งเท่ากับผลต่างของดัชนี
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
d :=แผนที่ว่างเปล่า
-
สำหรับแต่ละดัชนี i และค่า x เป็น nums ทำ
-
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
