หาคู่ (i, j) ให้ nums[i] + nums[j] + (i - j) สูงสุดใน Python

หาคู่ index i < j ที่ทำให้ nums[i] + nums[j] + (i - j) สูงสุด

ตัวอย่าง: nums = [6, 6, 2, 2, 2, 8] → 11 (เลือก index 0,1: 6+6+0-1=11)

แนวทาง (Greedy One Pass)

จัดรูป: (nums[i] + i) + (nums[j] - j) ต้องการ maximize

1. เก็บ large = nums[0] (ค่า nums[i] + i สูงสุดจนถึงตอนนี้)
2. วน i = 1..n-1:
   • large -= 1 (เพราะ i เพิ่มขึ้น 1 → nums[i]+i ลดลง 1 เทียบกับก่อนหน้า)
   • maxi = max(maxi, large + nums[i])
   • large = max(large, nums[i])

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums):
        large = nums[0]
        maxi = 0
        for i in range(1, len(nums)):
            large -= 1
            maxi = max(large + nums[i], maxi)
            large = max(large, nums[i])
        return maxi

ob = Solution()
nums = [6, 6, 2, 2, 2, 8]
print(ob.solve(nums))  # 11

อินพุต

[6, 6, 2, 2, 2, 8]

เอาต์พุต

11