ปัญหา
กำหนด list nums หา subsequence ที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) โดยที่ "ความต่างของค่า" = "ความต่างของ index" สำหรับทุกคู่ติดกัน
หา maximum sum ของ subsequence นี้
ตัวอย่าง: nums=[6,7,9,9,8,5] → 22
Subsequence: [6,7,9] ที่ index [0,1,3]
Diff values: 7-6=1, 9-7=2 | Diff indices: 1-0=1, 3-1=2 ✓
Key Insight
เงื่อนไข: nums[j] - nums[i] = j - i สำหรับ consecutive elements
→ nums[j] - j = nums[i] - i
→ ค่า (nums[i] - i) ต้องคงที่ตลอด subsequence!
วิธีแก้: Group by (value - index)
- คำนวณ key = nums[i] - i สำหรับทุก i
- Group elements โดย key นี้
- Sum ค่าในแต่ละ group
- หา max sum
โค้ด Python
from collections import defaultdict
class Solution:
def solve(self, nums):
d = defaultdict(int)
for i, x in enumerate(nums):
d[x - i] += x
return max(d.values())
# ทดสอบ
ob = Solution()
print(ob.solve([6, 7, 9, 9, 8, 5])) # 22
# Trace:
# i=0: 6-0=6 → d[6]=6
# i=1: 7-1=6 → d[6]=13
# i=2: 9-2=7 → d[7]=9
# i=3: 9-3=6 → d[6]=22
# i=4: 8-4=4 → d[4]=8
# i=5: 5-5=0 → d[0]=5
# Max: d[6]=22 (indices 0,1,3 → values 6,7,9)
ความซับซ้อน
- Time: O(n) - single pass
- Space: O(n) - hashmap
การพิสูจน์
สำหรับ subsequence ที่ valid: nums[i₁], nums[i₂], ..., nums[iₖ] โดย i₁ < i₂ < ... < iₖ
เงื่อนไข: nums[iⱼ] - nums[iⱼ₋₁] = iⱼ - iⱼ₋₁
→ nums[iⱼ] - iⱼ = nums[iⱼ₋₁] - iⱼ₋₁ = constant
ดังนั้น ทุก element ใน subsequence ต้องมี (value - index) เท่ากัน
LeetCode: 類似問題
เกี่ยวข้องกับ "Longest Arithmetic Subsequence" และ "Maximum Sum of Valid Subsequence"
