<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>.</p>

<p>You can perform any number of operations, where each operation involves selecting a <strong>subarray</strong> of the array and replacing it with the <strong>sum</strong> of its elements. For example, if the given array is <code>[1,3,5,6]</code> and you select subarray <code>[3,5]</code> the array will convert to <code>[1,8,6]</code>.</p>

<p>Return <em>the </em><strong><em>maximum</em></strong><em> length of a </em><strong><em>non-decreasing</em></strong><em> array that can be made after applying operations.</em></p>

<p>A <strong>subarray</strong> is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,2]
<strong>Output:</strong> 1
<strong>Explanation:</strong> This array with length 3 is not non-decreasing.
We have two ways to make the array length two.
First, choosing subarray [2,2] converts the array to [5,4].
Second, choosing subarray [5,2] converts the array to [7,2].
In these two ways the array is not non-decreasing.
And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing. 
So the answer is 1.
</pre>

<p><strong>Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The array is non-decreasing. So the answer is 4.
</pre>

<p><strong>Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,3,2,6]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing.
Because the given array is not non-decreasing, the maximum<!-- notionvc: 3447a505-d1ee-4411-8cae-e52162f53a55 --> possible answer is 3.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def findMaximumLength(self, nums: List[int]) -> int:
        '''
            Intuition : Monotonic stack with boundary conditions 
            If you look at each num in nums as it is added you can 
                - add it to the current total 
                - check if a maximum length and accumulated total priorly would have been satisfactory to combine (first boundary) 
                - based on the results of the prior step, if you did not combine everything already,
                    - check if a combined total in the stack on the end is greater than the next calculated combined total (combination of all other elements, second boundary) 
                    - if it is, then it is necessary to remove it, as it will cause our process to fail for finding the next greatest length 
                - when done with both, append a new item to the stack consisting of our new maximum length + 1, our new total, and twice the new total less the accumulated total 
            When done you can return the maximum length plus 1 

            The first boundary is that any item in the stack must have a combined total that is strictly greater than the current total 
            The second boundary is that any item in the stack must have a combined total lt the next combined total
            If a number is lte the current total, it'd be better to combine it, so you want to remove it from the left side of your stack
                While doing so, you want to catch the maximum length of it, and its accumulated total, so you are sure you maintain optimality 
            If a number is gte the next combined total, it would have been better to accumulate it instead, which will occur in a next step 
                While doing so, anything you reject must move you further from the goal, so setting it aside is valid 

            This is a greedy approach to the problem that can be shown to be optimal and sound 
        '''
        # can do in one run with loops inside without searching via base conditions 
        # track max length 
        max_length = 0
        # track accumulated total so far separately from maximum total so far 
        accumulated_total = 0
        total = 0
        # use a deque for your monotonic stack 
        monotonic_stack = collections.deque()
        # loop nums 
        for num in nums:
            # add to total each time  
            total += num 
            # then, while you have a monotonic stack and the first items combined totals is less than or equal to total 
            while monotonic_stack and monotonic_stack[0][2] <= total: 
                # remove it, and update your max length and the accumulated total. No need to track the combined totals. 
                max_length, accumulated_total, _ = monotonic_stack.popleft()
            # then, while you have a monotonic stack, and the last items combined totals is gte to the next combined total
            while monotonic_stack and monotonic_stack[-1][2] >= (2 * total - accumulated_total) : 
                # remove it entirely as it is not satisfactory 
                monotonic_stack.pop() 
            # when done on this pass, append the increase in max length, the total, and the new combined total 
            monotonic_stack.append((max_length + 1, total, 2 * total - accumulated_total))
        # return max length + 1 when done to account for 1 indexing in the problem space 
        return max_length + 1 

33200