O(N) in Python and O(N log N) in C
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem can be generally solved by dynamic programming. At the position i, we aim 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem can be generally solved by dynamic programming. At the position `i`, we aim to find the best position `j < i` that minimizes `sum[j+1:i+1]`. \n\nMy first solution employs segment tree that can range update prefix sum for visited numbers. Then, for number `nums[i]`, we look up the rightmost position `j < i` so that `f[j] <= sum(nums[j+1:i+1])`. The minimum group sum ends at `i` will be `f[i] = sum(nums[j+1:i+1])`. \n\nThe $O(N \\log N)$ solution implemented in C can pass the testdata. However, the testdata are too tough for my $O(N \\log N)$ Python solution with segment tree. A linear time solution can be improved from replacing the segment tree with a monotonic stack/queue `q` that stores the useful previous positions only. In other words, `f[s[0]] > f[s[1]] > ... > f[s[-1]]`. `q` is also a queue where the older, less ideal valid positions will be dequeued over time. The best `j` can be found in $O(1)$ as it is the firsmont element in `q`.\n\n# Linear Time Solution in Python\n\n## Complexity\n- Time complexity: $O(N)$\n\n## Code\n```\nclass Solution:\n    def findMaximumLength(self, nums: List[int]) -> int:\n        dp = [0] * (len(nums) + 1)\n        prefix_sums = list(accumulate(nums, initial=0))\n        queue = deque()\n        prev = 0\n        for i, val in enumerate(nums, 1):\n            while queue and queue[0][0] >= -prefix_sums[i]:\n                _, prev = queue.popleft()\n            dp[i] = dp[prev] + 1\n            cost = -prefix_sums[i] - (prefix_sums[i]-prefix_sums[prev])\n            while queue and queue[-1][0] <= cost:\n                queue.pop()                      \n            queue.append([cost, i])\n        return dp[-1]\n```\n# Slower Solution in C\n\n## Complexity\n- Time complexity: $O(N \\log N)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n## Code\n```\n#include <stdlib.h>\n#define min(a, b) ((a) < (b) ? (a) : (b))\n#define max(a, b) ((a) > (b) ? (a) : (b))\n\nlong long int t[400010], lazy[400010];\n\nvoid push(int v) {\n    t[v*2] += lazy[v];\n    lazy[v*2] += lazy[v];\n    t[v*2+1] += lazy[v];\n    lazy[v*2+1] += lazy[v];\n    lazy[v] = 0;\n}\n\nvoid update(int v, int tl, int tr, int l, int r, int addend) {\n    if (l > r) \n        return;\n    if (l == tl && tr == r) {\n        t[v] += addend;\n        lazy[v] += addend;\n    } else {\n        push(v);\n        int tm = (tl + tr) / 2;\n        update(v*2, tl, tm, l, min(r, tm), addend);\n        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);\n        t[v] = max(t[v*2], t[v*2+1]);\n    }\n}\n\nint query(int v, int tl, int tr, int l, int r) {\n    if (tl > r || tr < l || t[v] < 0) \n        return -1;\n    if (tl == tr)\n        return tl;\n    push(v);\n    int tm = (tl + tr) / 2;\n    int right = query(v*2+1, tm+1, tr, max(l, tm+1), r);\n    if (right != -1)\n        return right; \n    return query(v*2, tl, tm, l, min(r, tm));\n}\n\nint findMaximumLength(int* nums, int numsSize) {\n    memset(t, 0, sizeof(t));\n    memset(lazy, 0, sizeof(lazy));\n    int dp[100002];\n    long long int prefix_sums[100002];\n    dp[0] = 0;\n    prefix_sums[0] = 0;\n    int i, j;\n    for (i = 0; i < numsSize; ++i) {\n        prefix_sums[i+1] = prefix_sums[i] + nums[i];\n        update(1, 0, numsSize, 0, i, nums[i]);\n        j = query(1, 0, numsSize, 0, i);\n        dp[i+1] = dp[j] + 1;\n        update(1, 0, numsSize, i+1, i+1, -(prefix_sums[i+1]-prefix_sums[j]));\n    }\n    return dp[numsSize];\n}```
['Dynamic Programming', 'Segment Tree', 'C', 'Monotonic Stack', 'Monotonic Queue', 'Python3']