पायथन में सूची को गैर-बढ़ते क्रम में बदलने के लिए आवश्यक ऑपरेशन्स की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। अब एक ऑपरेशन पर विचार करें जहां हम दो लगातार मान लेते हैं और उन्हें उनके योग लेकर एक मान में मर्ज करते हैं। हमें न्यूनतम ऑपरेशन्स की संख्या ज्ञात करनी है ताकि सूची गैर-बढ़ते क्रम में बदल जाए।

इसलिए, यदि इनपुट nums = [2, 6, 4, 10, 2] जैसा है, तो आउटपुट 2 होगा, क्योंकि हम [2, 6] को मर्ज करके [8, 4, 10, 2] प्राप्त कर सकते हैं और फिर [8, 4] को मर्ज करके [12, 10, 2] प्राप्त कर सकते हैं।

हल करने के चरण

• यदि nums खाली है, तो 0 लौटाएं

• nums के अंत में -infinity डालें

• N := nums का आकार

• dp := आकार N की सूची और 0 से भरें

• arr := आकार N की सूची और 0 से भरें

• p := arr का आकार

• arr[p-1] := nums[N-1]

• arr[p-2] := nums[N-2]

• i के लिए N - 3 से 0 तक, 1 से घटाते हुए, करें

  • j := i

  • x := nums[j]

  • जब तक j < N - 1 और x < arr[j + 1], करें

    • j := j + 1

    • x := 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]

आउटपुट

2