LC 2945. 找到最大非递减数组的长度

https://leetcode.cn/problems/find-maximum-non-decreasing-array-length/

跟着题解差不多看懂了整个过程，好像得到两个重要特性：

`f[i]` 是单调递增的
`s[i] + last[i]` 这个也是单调递增
对于i来说，选择的就是最大的j, `s[i] >= s[j] + last[j]`.

所以可以使用单调递增的队列，时间复杂度就是在O(n).

class Solution:
    def findMaximumLength(self, nums: List[int]) -> int:
        n = len(nums)
        s = [0] * (n + 1)
        for i in range(n):
            s[i + 1] = s[i] + nums[i]
        f = [0] * (n + 1)
        last = [0] * (n + 1)
        from collections import deque
        q = deque([0])
        for i in range(1, n + 1):
            while len(q) > 1 and s[q[1]] + last[q[1]] <= s[i]:
                q.popleft()

            f[i] = f[q[0]] + 1
            last[i] = s[i] - s[q[0]]

            while q and s[q[-1]] + last[q[-1]] >= s[i] + last[i]:
                q.pop()
            q.append(i)
        return f[-1]