পাইথনে লিস্টকে নন-ইনক্রিজিং বানাতে ন্যূনতম মার্জ অপারেশন গণনা

একটি সংখ্যার লিস্ট nums দেওয়া আছে। একটি অপারেশনে দুটি সংলগ্ন মান যোগ করে একটা মানের সাথে রিপ্লেস করা যায়। লিস্টকে নন-ইনক্রিজিং (Non-increasing) বানাতে ন্যূনতম কতটি অপারেশন লাগবে তা বের করতে হবে।

উদাহরণ: nums = [2, 6, 4, 10, 2] → আউটপুট 2। (মার্জ [2,6]→8, তারপর [8,4]→12 → ফাইনাল [12,10,2])।

সমাধানের ধাপসমূহ (DP + মনোটোনিক স্ট্যাক বা গ্রিডি)

যদি nums খালি হয়, ০ রিটার্ন।
nums.append(-inf) (সেন্টিনেল)। N := লেন্থ।
dp := আকার N শূন্য অ্যারে, arr := আকার N শূন্য অ্যারে।
arr[-1] = nums[-1], arr[-2] = nums[-2]।
i = N-3 থেকে 0 পর্যন্ত:
- j = i, x = nums[j]
- যখন j < N-1 এবং x < arr[j+1]:
  - j++, x += nums[j]
- dp[i] = j - i + dp[j+1]
- arr[i] = x
dp[0] রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, nums):
        if not nums:
            return 0
        nums.append(float("-inf"))
        N = len(nums)
        dp = [0] * N
        arr = [0] * N
        arr[-1] = nums[-1]
        arr[-2] = nums[-2]
        for i in range(N - 3, -1, -1):
            j = i
            x = nums[j]
            while j < N - 1 and x < arr[j + 1]:
                j += 1
                x += nums[j]
            dp[i] = j - i + dp[j + 1]
            arr[i] = x
        return dp[0]

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

ইনপুট

[2, 6, 4, 10, 2]