[Python3] Monotonic Stack O(n)
dp[i] is the length of longest non-decreasing array from nums[0] to nums[i-1]. last[i] is last number in the corresponding dp[i] array. j = stack[i] represents 
`dp[i]` is the length of longest non-decreasing array from `nums[0]` to `nums[i-1]`. `last[i]` is last number in the corresponding `dp[i]` array. `j = stack[i]` represents `presum[i] + last[i]` is the largest until the index `j`.\nFor each `i`, we find largest `j = stack[l]` such that `presum[j] + last[j] <= presum[i]` i.e. (`last[j] <= nums[j] + ... + nums[i-1]`).\n```\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        n = len(nums)\n        presum = [0] * (n + 1)\n        for i in range(n):\n            presum[i+1] = presum[i] + nums[i]\n        \n        last = [0] * (n + 1)\n        stack = [0] * (n + 1)\n        dp = [0] * (n + 1)\n        l = 0\n        r = 1\n        for i in range(1, n + 1):\n            while l + 1 < r and presum[i] >= presum[stack[l + 1]] + last[stack[l + 1]]:\n                l += 1\n            last[i] = presum[i] - presum[stack[l]]\n            dp[i] = dp[stack[l]] + 1\n            while l < r and presum[i] + last[i] < presum[stack[r - 1]] + last[stack[r - 1]]:\n                r -= 1\n            stack[r] = i\n            r += 1\n        return dp[-1]\n```
['Dynamic Programming', 'Monotonic Stack']