মনে করুন, nums নামে n সংখ্যক ইন্টিজারের একটি অ্যারে আছে। nums-এ প্রতিটি মান এর 'শক্তি'কে প্রতিনিধিত্ব করে। অ্যারেটি 'বৈধ' হবে যদি এর দৈর্ঘ্য দুইর চেয়ে বেশি হয় এবং অ্যারেটির প্রথম এবং শেষ মান সমান হয়। আমাদের অ্যারেটি থেকে এলিমেন্ট ডিলিট করে এটি বৈধ করতে হবে যাতে বাকিগুলো শর্ত পূরণ করে। আউটপুট হিসেবে, আমরা অ্যারেটির সর্বোচ্চ সম্ভাব্য শক্তি মান রিটার্ন করব যা অ্যারেটির সব শক্তি মান যোগ করে পাওয়া যায়।
সুতরাং, যদি ইনপুট হয় nums = [3, 4, 5, 3, 4], তবে আউটপুট হবে 16।
যদি আমরা nums অ্যারেটির প্রথম মান 3 মুছে দি, তবে এটি হয়ে যায় [4, 5, 3, 4]। এটি একটি বৈধ অ্যারে এবং শক্তিগুলোর যোগফল 4 + 5 + 3 + 4 = 16। দেয়া ইনপুট থেকে যেকোনো বৈধ অ্যারেতে এটি সর্বোচ্চ সম্ভাব্য যোগফল।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
table := একটি নতুন ম্যাপ
prefix := 0 মান দিয়ে ইনিশিয়ালাইজ করা একটি নতুন তালিকা
negative := 0 মান দিয়ে ইনিশিয়ালাইজ করা একটি নতুন তালিকা
nums-এ প্রতিটি ইন্ডেক্স i এবং মান j-এর জন্য, করুন
যদি j table-এ না থাকে, তবে
table[j] := একটি নতুন জোড়া (i, 0)
অন্যথায়,
table[j, -1] := i
prefix-এ একটি নতুন এলিমেন্ট যোগ করুন যা prefix-এর লাস্ট এলিমেন্ট + j-এর সমান
negative-এর লাস্ট এলিমেন্ট ডুপ্লিকেট করুন
যদি j < 0, তবে
negative-এর লাস্ট এলিমেন্ট := negative-এর লাস্ট এলিমেন্ট + j
ans := নেগেটিভ ইনফিনিটি
table-এ সব ভ্যালু জোড়া (i,j) এর জন্য, করুন
যদি j != 0 হয়, তবে
sm1 := prefix[j+1] - prefix[i]
যদি j > i+1 হয়, তবে
sm2 := negative[j] - negative[i+1]
অন্যথায়,
sm2 := 0
ans := ans এবং (sm1 - sm2) এর মধ্যে সর্বোচ্চ
ans রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন −
def solve(nums):
table = {}
prefix = [0]
negative = [0]
for i, j in enumerate(nums):
if j not in table:
table[j] = [i, 0]
else:
table[j][-1] = i
prefix += prefix[-1] + j,
negative += negative[-1],
if j < 0:
negative[-1] += j
ans = float('-inf')
for i,j in table.values():
if j != 0:
sm1 = prefix[j+1] - prefix[i]
sm2 = negative[j] - negative[i+1] if j > i+1 else 0
ans = max(ans, sm1 - sm2)
return ans
print(solve([3, 4, 5, 3, 4]))
ইনপুট
[3, 4, 5, 3, 4]
আউটপুট
16
