Tìm cặp (i,j) tối đa hóa nums[i]+nums[j]+(i-j) trong Python

Cho list nums, tìm cặp (i, j) với i < j sao cho nums[i] + nums[j] + (i - j) lớn nhất.

Ví dụ: nums = [6, 6, 2, 2, 2, 8] → 11 (chọn 2 số 6 đầu: 6+6+0-1=11).

Biến đổi: nums[i] + nums[j] + i - j = (nums[i] + i) + (nums[j] - j). Duyệt j từ 1..n-1, giữ large = max(large-1, nums[j-1]) (tương đương max nums[i]+i với phạt khoảng cách).

Ví dụ triển khai

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

Đầu vào

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

Đầu ra

11