DP + Heap solution with detailed explanation
\nLet dp(i) be: the maximum possible number of subarrays for 0\~i\nLet last_sm(i) be: the sum of last subarray, when splitted optimally according to dp(i)\nLet 
\nLet **dp(i)** be: the maximum possible number of subarrays for 0\\~i\nLet **last_sm(i)** be: the sum of last subarray, when splitted optimally according to dp(i)\nLet "**slow**" be: the splitting point for the last subarray group ended at "i". 0\\~slow can contain many groups, slow\\~i is only one group. For all slow<i, some "slow" indexes are not valid (cannot make increasing sequence), some are valid but not optimal (can make increasing sequence but not maximum number of groups), only one is valid and optimal. We need to find the valid and optimal "slow" index and pair it with "i".\n\nSuppose we are now at index "i", and suppose we already have all the **dp** and **last_sm** calculated for indexes 0\\~(i-1). If we can find all the "slow" indexes that makes last subarray "slow\\~i" valid (valid but not necessary optimal), then\n**Important observations:**\n1. For invalid "slow" indexes, they might be useful for the following "i", we need to keep them (cannot delete).\n2. For valid "slow" indexes, the right most "slow" index is the optimal one to pair with current "i". The rest valid "slow" indexes are not only useless for the current "i", but **also useless for the following "i"**, we can safely delete them. \n\n\nThis lead us to the idea of heap que. We keep all the in-valid "slow" indexes in the heap, and pop out all the valid "slow" indexes. For the popped out indexes, we pick the right most one and pair it with current "i" to make optimal splitting point for the last group ended at "i". We then have:\nlast_sm(i) = sum(slow\\~i)\ndp(i) = dp(slow)+1\ndp(n-1) is the final result.\n\nIn reality, a heap doesn\'t know which "slow" index is valid and thus doesn\'t know which one to pop out. We need to do it a different way.\nIt is easy to see that: in order for "slow" to be valid, we have:\nsum(slow\\~i) >= last_sm(slow)\n    => sum(0\\~i) - sum(0\\~slow) >= last(slow)\n    => sum(0\\~i) >= last(slow) + sum(0\\~slow)\nSo we push "last(slow)+sum(0\\~slow)" into the heap and pop out all values that <= sum(0\\~i). This way, all popped out values correspond to valid "slow" indexes. The right most amomng them is the one we choose to pair with current "i".\n\nIn reality, we push [last(slow) + sum(0\\~slow), dp(slow), sum(0\\~slow)] into the heap. The first value indicates whether the popped out value is valid or not.  Among all the popped values, the one with the biggest [2nd value, 3rd value] is the right most "slow" index, we pair it with "i".\n\n\nTime complexity: O(nlgn)\n\n# Code\n``` python\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        # current last_g_sum = prefix - prev_prefix\n        # prefix - prev_prefix >= prev_last_g_sum\n        #       => prefix >= prev_last_g_sum + prev_prefix\n        # heapq: [ last_g_sum + prefix, g_cnt, prefix ]\n        hq,prefix = [],0\n        prev_cnt,prev_prefix = 0,0\n        for v in nums:\n            prefix += v\n            while hq and hq[0][0]<=prefix:\n                _,prev_cnt0,prev_prefix0 = heapq.heappop(hq)\n                if (prev_cnt0,prev_prefix0) >= (prev_cnt,prev_prefix):\n                    prev_cnt,prev_prefix = prev_cnt0,prev_prefix0\n            last_g_sm = prefix-prev_prefix\n            heapq.heappush(hq,(last_g_sm+prefix,prev_cnt+1,prefix))\n        return prev_cnt+1\n```
['Python3']