পাইথনে উপাদান পুনর্বিন্যাস করে তালিকার সর্বোচ্চ পাওয়ার মান নির্ণয়

ধরুন, N সংখ্যক ধনাত্মক সংখ্যার একটি তালিকা nums রয়েছে। আমরা তালিক থেকে যেকোন একটি মান বেছে নিয়ে তা যেকোন স্থানে সরিয়ে দিতে পারি (স্ব্যাপ না করে)। আমরা কোনো উপাদান সরাতে বাধ্য নই। লক্ষ্য হল তালিকার সর্বোচ্চ সম্ভাব্য চূড়ান্ত পাওয়ার নির্ণয় করা। তালিকার পাওয়ার বলতে সমস্ত সূচক i এর জন্য (i+1) * value_at_index এর যোগফল বোঝায়।

$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$

উদাহরণস্বরূপ, ইনপুট nums = [6, 2, 3] হলে আউটপুট হবে ২৬, কারণ ৬ কে শেষে নিয়ে আসলে তালিকা হয় [2, 3, 6] এবং পাওয়ার: (2×1) + (3×2) + (6×3) = ২৬।

সমাধানের ধাপসমূহ

P := [0] মানով একটি তালিকা
base := 0
তালিকা A এর প্রতিটি সূচক i এবং মান x এর জন্য:
- P তালিকায় P[-1] + x যোগ করুন
- base := base + (i+1) * x
ans := base
A তালিকার প্রতিটি সূচক i এবং মান x এর জন্য:
- j = 0 থেকে len(A) পর্যন্ত লুপ চালান:
  - ans := max(ans, base + P[i] - P[j] - (i - j) * x)
ans ফেরত দিন

উদাহরণ কোড

class Solution:
    def solve(self, A):
        P = [0]
        base = 0
        for i, x in enumerate(A, 1):
            P.append(P[-1] + x)
            base += i * x
        ans = base
        for i, x in enumerate(A):
            for j in range(len(A) + 1):
                ans = max(ans, base + P[i] - P[j] - (i - j) * x)
        return ans

ob = Solution()
nums = [6, 2, 3]
print(ob.solve(nums))

ইনপুট

[6, 2, 3]