পাইথনে nums[i] + nums[j] + (i - j) এক্সপ্রেশন ম্যাক্সিমাইজ করা

সমস্যা বিবরণ

একটি সংখ্যা লিস্ট nums দেওয়া আছে। ইনডেক্স পেয়ার (i, j) খুঁজে বের করতে হবে যেখানে i < j এবং nums[i] + nums[j] + (i - j) ম্যাক্সিমাম হয়।

উদাহরণ

Input:  nums = [6, 6, 2, 2, 2, 8]
Output: 11
ব্যাখ্যা: i=0, j=1 → 6 + 6 + (0-1) = 11

গাণিতিক রূপান্তর

nums[i] + nums[j] + (i - j)
= (nums[i] + i) + (nums[j] - j)

তাই প্রতিটি j এর জন্য, i < j এমন nums[i] + i এর ম্যাক্সিমাম খুঁজে বের করলে হয়।

অ্যালগরিদম (O(n) - এক পাস)

1. max_left = nums[0] + 0 (i=0 এর জন্য)
2. ans = 0
3. j = 1 থেকে n-1 পর্যন্ত লুপ:
   • ans = max(ans, max_left + nums[j] - j)
   • max_left = max(max_left, nums[j] + j)
4. ans রিটার্ন

পাইথন কোড

class Solution:
    def solve(self, nums):
        max_left = nums[0]  # nums[0] + 0
        ans = 0
        
        for j in range(1, len(nums)):
            # বর্তমান j দিয়ে বেস্ট পেয়ার
            ans = max(ans, max_left + nums[j] - j)
            # max_left আপডেট
            max_left = max(max_left, nums[j] + j)
        
        return ans

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

প্রদত্ত কোডের লজিক (একই কিন্তু ভিন্ন ফরমুলেশন)

large = nums[0]
maxi = 0
for i in range(1, len(nums)):
    large -= 1           # (nums[i-1] + (i-1)) - 1 = nums[i-1] + i - 2
    maxi = max(maxi, large + nums[i])
    large = max(large, nums[i])

এখানে large ট্র্যাক করে max(nums[k] - k) for k < i। উভয়ই সমতুল্য।

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n) — একক পাস
• স্থান জটিলতা: O(1) — কনস্ট্যান্ট স্পেস

উপসংহার

• এক্সপ্রেশন রি-অ্যারেঞ্জ করে (nums[i]+i) + (nums[j]-j) বানান
• রানিং ম্যাক্সিমাম মেইনটেইন করে O(n) সমাধান
• স্লাইডিং উইন্ডো / কাদেনস অ্যালগরিদমের ভ্যারিয়েন্ট