একটি নম্বর লিস্ট nums দেওয়া আছে। ইনডেক্স পেয়ার (i, j) যাতে i < j এবং j - i > 1 (নন-কনsekutিভ)। তাদের মধ্যে ন্যূনতম যোগফল বের করুন।
ইনপুট উদাহরণ
nums = [3, 4, 2, 2, 4]আউটপুট: 5 (3+2=5, ইনডেক্স ০ এবং ২। ২+২=৪ সম्भব নয় কারণ এডজেসেন্ট)।
অ্যালগরিদম
min_seen = nums[0](আগের সবচেয়ে ছোট মান)।ans = inf।i = 2থেকেn-1পর্যন্ত লুপ:ans = min(ans, min_seen + nums[i]), তারপরmin_seen = min(min_seen, nums[i-1])।
পাইথন কোড
def solve(nums):
n = len(nums)
min_seen = nums[0]
ans = float("inf")
for i in range(2, n):
ans = min(ans, min_seen + nums[i])
min_seen = min(min_seen, nums[i - 1])
return ans
# টেস্ট
print(solve([3, 4, 2, 2, 4])) # 5ব্যাখ্যা
ইনডেক্স i-এর জন্য ভ্যালিড পার্টনার হলো 0 ... i-2। min_seen আমরা i-2 পর্যন্ত মিনিমাম ট্র্যাক করি। এক পাসে O(n) সমাধান।
