[Simple] [Heap] [Monotonic Stack] [Optimized O(n)] 8 line Python Solution Explained in detail
\n\n# Please Upvote!\n\n# Intuition\nGiven an array A[i], i = 0, ..., n-1 with running totals S[i] write the maximum non-decreasing array as $F[A]i$ then F(A) =
![crying.jpg](https://assets.leetcode.com/users/images/1827a9a4-9874-4be9-81b8-0bc13cadf915_1700936341.9665794.jpeg)\n\n# Please Upvote!\n\n# Intuition\nGiven an array `A[i], i = 0, ..., n-1` with running totals `S[i]` write the maximum non-decreasing array as $F[A]_i$ then `F(A) = max((F(A[:j]) + [S[n] - S[j]] for j where (S[n] - S[j]) >= F(A[:j])[-1] key=len)` As the last element must be some suffix sum.\n\nIn particular `F(A)[-1] = S[n] - S[j*]` where `j*` maximizes the above.\n\nSo lets define: `last_val(j) = F(A[:j])[-1]` `f(j) = len(F(A[:j])` and `j* = max(j\' < j, by f(j\'), where last_val(j\') <= (S[j] - S[j\'])) ` (defined recursively). Then `f(j) = f(j*) + 1` and `last_val(j) = (S[j]  - S[j*])`\n\nBy using precomputed values of `last_val(j)` and `f(j)` whe can calculate the future values inductively.\n\n\n# Approach\nWe can write a simple unoptimized solution:\n\n```python3\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        n = len(nums)\n        f = [0] * n\n        last_val = [0] * n\n        sums = [0] * n\n        f[0] = 1\n        S = 0\n        for j in range(n):\n            sums[j] = S = S + nums[j]\n            _, i = max(((f[i], i) for i in range(j) if last_val[i] <= sums[j] - sums[i]), default=(0, -1))\n            if i == -1:\n                f[j] = 1\n                last_val[j] = sums[j]\n            else:\n                f[j] = f[i] + 1\n                last_val[j] = sums[j] - sums[i]\n        return f[n-1]\n```\n\nTo optimize this we write `g(i) = last_val(i) + S[i]`. Then we are filtering only to `i` that satisfy `last_val(i) <= (S[j] - S[i])` i.e. `g(i) = last_val(i) +  S[i] <= S[j]`.\n\nWe can use a heap to restrict to these values and then just take the max of over those values.\n\n```\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        q, d, s, S = [], 0, 0, 0\n        for x in nums:\n            S += x\n            while q and q[0][0] <= S:\n                _, d_, s_ = heapq.heappop(q)\n                if (d_, s_) >= (d, s): d, s = d_, s_\n            heapq.heappush(q, (2 * S - s, d + 1, S))\n        return d + 1\n\n```\n\nFurthermore we can observer that `F(i)` is non decreasing as we could always at least just add `A[i]` to `last_val(i-1)` to get the same length, so we can replace the heap with a monotone queue, where we throw away values `g(i\') > g(i), i\' < i` from the queue. \n\n# Complexity\n- Time complexity: \n  - max: $$O(n ^ 2)$$\n  - heap: $$O(n \\log n)$$\n  - stack: $$O(n)$$\n- Space complexity: $$O(n)$$\n# Code\n\n```\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        q, d, s, S = collections.deque(), 0, 0, 0\n        for x in nums:\n            S += x\n            while q and q[0][0] <= S:\n                _, d_, s_ = q.popleft()\n                if (d_, s_) >= (d, s): d, s = d_, s_\n            while q and q[-1] > (2 * S - s, d + 1, S): q.pop()\n            q.append((2 * S - s, d + 1, S))\n        return d + 1\n\n
['Heap (Priority Queue)', 'Python3']