ধরুন, আমাদেরকে পূর্ণসংখ্যা সম্বলিত একটি অ্যারে দেওয়া হয়েছে। আমরা একটি অপারেশন করতে পারি যেখানে আমরা অ্যারে[i] এর মানকে এর বর্গ মান দিয়ে প্রতিস্থাপন করতে পারি; বা অ্যারে[i] * অ্যারে[i]। এই ধরনের শুধুমাত্র একটি অপারেশন অনুমোদিত এবং আমাদের অপারেশনের পরে সর্বাধিক সম্ভাব্য সাবারের যোগফল ফেরত দিতে হবে। সাবয়ারে খালি হতে পারে না৷
৷সুতরাং, যদি ইনপুট অ্যারে =[4, 1, -2, -1] এর মত হয়, তাহলে আউটপুট হবে 17।
যদি আমরা অ্যারে [0]-এর মানকে এর বর্গ মান দিয়ে প্রতিস্থাপন করি, তাহলে অ্যারেটি [16, 1, -2, -1] হয়ে যায়। এটি থেকে সর্বাধিক সাবয়ারে সম্ভব [16, 1], এবং এটির সর্বাধিক যোগফল মান 16 + 1 =17।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- dp1 :=নেতিবাচক অসীম মান ধারণকারী একটি নতুন তালিকা
- dp2 :=নেতিবাচক অসীম মান ধারণকারী একটি নতুন তালিকা
- অ্যারের প্রতিটি সংখ্যার জন্য, করুন
- dp1-এর শেষে সর্বাধিক (dp1 + num-এর শেষ উপাদান), num) সন্নিবেশ করুন
- dp2-এর শেষে সর্বাধিক (dp1 + num^2-এর দ্বিতীয় শেষ উপাদান), num^2, (dp2 + num-এর শেষ উপাদান)) সন্নিবেশ করুন
- dp2 এর সর্বোচ্চ উপাদান ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(array):
dp1 = [float('-inf')]
dp2 = [float('-inf')]
for num in array:
dp1.append(max(dp1[-1] + num, num))
dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
return max(dp2)
print(solve([4, 1, -2, -1])) ইনপুট
[4, 1, -2, -1]
আউটপুট
17
