Problem statement

https://binarysearch.com/problems/Turn-Into-Non-Increasing-List/

Solution

First of all, the main difficulty that we can have negative numbers in our array, if we have all positive, I think it has linear time solution. Let dp[i] is the the minimum number of operations to make A[i:] a non-increasing array. We calcualte it from the end. To compute dp[i], we greedily find a minimal sub-array nums[i..j] such that: sum(nums[i..j]) > vals[j+1], where vals[j+1] is the merge value for dp[j+1].

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, A):
        if not A: return 0
        A += [float("-inf")]
        n = len(A)
        dp, vals = [0] * n, A[:]
        for i in range(n - 3, -1, -1):
            j, x = i, A[i]
            while j < n - 1 and x < vals[j + 1]:
                j += 1
                x += A[j]
            dp[i] = j - i + dp[j + 1]
            vals[i] = x

        return dp[0]