Greedy Approach | Optimal Approach Explained
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst intuition is that a monotonic stack is the correct answer. \nSecond intuition is 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst intuition is that a monotonic stack is the correct answer. \nSecond intuition is that a greedy search can be used if we use boundary conditions that are satisfiable and can be shown to be optimal. \n\nThe first condition we want to satisfy is that our monotonic array tracks only increasing array sizes \n\nThe second condition we want to satisfay is that our monotonic array tracks only monotonically increasing arrays \n\nThe third condition we want to satisfy is that our monotonic array considers the increasing total value of the array as we move left to right \n\nWe can summarize these into two boundary conditions. \n\nThe first is that we want to make sure that the combined total of any item at the front of the monotonic stack is always greater than our current total (otherwise, we should combine it). If it is not, we want to grab whatever maximum length it held and its accumulated total (we won\'t worry about the combined, since we\'ll be combining with it shortly!)\n\nThe second is that any item left after that with a combined total that is not less than our combined total is one that we could not combine with. Since we want to avoid searching, we reject it out of hand, as the current answer is probably better (this is the greedy part where we trim the right hand side). \n\nOur combined total in all cases is twice our total less our accumulated total. We use twice our total less our accumulated total so that our accumulated total, which has been increasing as we remove left hand items to combine, will maintain its validity against other sections as we go along. This lets us know which segments are valid to maintain in our subarray, essentially pruning the elements from the list that we do not wish to utilize. This can be seen as guaranteeing that the next number we add is large enough to validate its inclusion and should not be sub-combined in the process. \n\nThen, when done with both left and right pruning, we need to add our newest item, which is a node in our monotonic stack with maximum length + 1, our total that includes the most recent num, and the new combined total of twice the total less the accumulated total. \n\nRemember, accumulated total updates in the first boundary condition, essentially merging elements together in the best possible greedy fashion while they have a combined total that is strictly not greater than our new total. \n\nThen, we use the new accumulated total to reject those nodes of combinations that would lead to combined totals that are strictly more than our next monotonic stacks combined total. This means our monotonic stack maintains only the increasing length of the array and always is ready to accept our next node as valid in the sequence.\n\nThe next node should always have a maximum length of plus 1 to the current maximum length to satisfy that increasing aspect. The accumulated total of the new node should just be total AT THIS POINT IN THE TRAVERSAL. The next combined total is twice the current total, less the current accumulated total. This means that any new node after will satisfy a combination of the accumulated total, and the next total in this process. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo approach the problem, use \n- continuously increasing max length of arrays \n- continuously increasing running total \n- an accumulated total that increases through combinations \n- a combined total that is twice the continuously increasing running total less the accumulated total so far. This lets you guard for the next number that would be vaild to include in the subarray. \n\nLoop over nums in one pass, using subloops to prune as you go through the tree options. \n\n# Complexity\n- Time complexity: N log N\n    - You do loop over N values to go through nums \n        - during which you do log of N work to prune the values at worst in the subloops. It must be log(N) as you are doing a tree traversal pruning of the problem space.   \n\n- Space complexity: log(N) \n    - You only store the valid tree traversal components, which is a path of the tree, at worst log(N) as you cannot traverse the whole tree in a valid approach for the problem space. This can be seen by looking at test case 2\'s breakdown.  \n\n# Code\n```python3 []\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        \'\'\'\n            Intuition : Monotonic stack with boundary conditions \n            If you look at each num in nums as it is added you can \n                - add it to the current total \n                - check if a maximum length and accumulated total priorly would have been satisfactory to combine (first boundary) \n                - based on the results of the prior step, if you did not combine everything already,\n                    - 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) \n                    - if it is, then it is necessary to remove it, as it will cause our process to fail for finding the next greatest length \n                - 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 \n            When done you can return the maximum length plus 1 \n\n            The first boundary is that any item in the stack must have a combined total that is strictly greater than the current total \n            The second boundary is that any item in the stack must have a combined total lt the next combined total\n            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\n                While doing so, you want to catch the maximum length of it, and its accumulated total, so you are sure you maintain optimality \n            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 \n                While doing so, anything you reject must move you further from the goal, so setting it aside is valid \n\n            This is a greedy approach to the problem that can be shown to be optimal and sound \n        \'\'\'\n        # can do in one run with loops inside without searching via base conditions \n        # track max length \n        max_length = 0\n        # track accumulated total so far separately from maximum total so far \n        accumulated_total = 0\n        total = 0\n        # use a deque for your monotonic stack \n        monotonic_stack = collections.deque()\n        # loop nums \n        for num in nums:\n            # add to total each time  \n            total += num \n            # then, while you have a monotonic stack and the first items combined totals is less than or equal to total \n            while monotonic_stack and monotonic_stack[0][2] <= total: \n                # remove it, and update your max length and the accumulated total. No need to track the combined totals. \n                max_length, accumulated_total, _ = monotonic_stack.popleft()\n            # then, while you have a monotonic stack, and the last items combined totals is gte to the next combined total\n            while monotonic_stack and monotonic_stack[-1][2] >= (2 * total - accumulated_total) : \n                # remove it entirely as it is not satisfactory \n                monotonic_stack.pop() \n            # when done on this pass, append the increase in max length, the total, and the new combined total \n            monotonic_stack.append((max_length + 1, total, 2 * total - accumulated_total))\n        # return max length + 1 when done to account for 1 indexing in the problem space \n        return max_length + 1 \n\n```
['Python3']