পাইথনে অপারেশনের পর সর্বাধিক সাবঅ্যারে যোগফল খুঁজে বের করার প্রোগ্রাম

আমাদের একটি অ্যারে দেওয়া আছে যাতে পূর্ণসংখ্যা রয়েছে। আমরা একটি অপারেশন পারফর্ম করতে পারি যেখানে array[i]-এর মানকে এর বর্গমূল দিয়ে প্রতিস্থাপন করতে পারি; অর্থাৎ array[i] * array[i]। এই ধরনের অপারেশন শুধু একবার অনুমোদিত এবং আমাদের অপারেশনের পর সর্বাধিক সম্ভাব্য সাবঅ্যারে যোগফল রিটার্ন করতে হবে। সাবঅ্যারে খালি হতে পারবে না।

উদাহরণস্বরূপ, ইনপুট array = [4, 1, -2, -1] হলে আউটপুট হবে 17।

যদি array[0]-এর মানকে এর বর্গমূল দিয়ে প্রতিস্থাপন করি, অ্যারে হবে [16, 1, -2, -1]। এই থেকে সম্ভাব্য সর্বাধিক সাবঅ্যারে হলো [16, 1], এবং এর সর্বাধিক যোগফল মান 16 + 1 = 17।

সমাধানের ধাপসমূহ (DP)

• dp1 := [float('-inf')] দিয়ে একটি লিস্ট শুরু করুন

• dp2 := [float('-inf')] দিয়ে একটি লিস্ট শুরু করুন

• array-এর প্রতিটি num এর জন্য:

  • max(dp1[-1] + num, num)-কে dp1-এর শেষে যোগ করুন

  • max(dp1[-2] + num**2, num**2, dp2[-1] + num)-কে dp2-এর শেষে যোগ করুন

• 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