My Solution
\n/**\n * let `n` be the length of the vector `nums`\n * let `presums[i]` be sum(nums[0], nums[1], ..., nums[i])\n *\n * the dp solution is employed.\n * 1. dp[
```\n/**\n * let `n` be the length of the vector `nums`\n * let `presums[i]` be sum(nums[0], nums[1], ..., nums[i])\n *\n * the dp solution is employed.\n * 1. dp[i] stands for the maximum length of a non-decreasing array\n *    that can be made after applying operations\n *    from the subarray {nums[0], nums[1], nums[i]}\n *    one observation: dp[i] is non-decreasing because nums[i] can always\n *                     be added to last group when nums[i] comes\n *                     in the worst cases\n * 2. last[i] stands for the smallest last element when dp[i] is made\n *\n * let\'s take an example to explain it.\n * nums = [4, 3, 2, 6]\n * ------------------------------\n * i\\ | nums[i] | dp[i] | last[i]\n * ---|---------|-------|--------\n * 0  |       4 |     1 |       4\n * ---|---------|-------|--------\n * 1  |       3 |     1 |       7\n * ---|---------|-------|--------\n * 2  |       2 |     2 |       5\n * ---|---------|-------|--------\n * 3  |       6 |     3 |       6\n * ------------------------------\n *\n * if presums[i] - presums[j] >= last[j], dp[i] can be got from dp[j] + 1\n * so dp[i] = max(dp[j] + 1, for all j if presums[i] - presums[j] >= last[j])\n * presums[i] - presums[j] >= last[j] <=> presums[i] >= presums[j] + last[j]\n *\n * assume j1 < j2 and presums[j1] + last[j1] >= presums[j2] + last[j2]\n * 1. if presums[i] >= presums[j1] + last[j1], presums[i] >= presums[j2] + last[j2]\n * 2. because j1 < j2, dp[j1] <= dp[j2]\n * so j1 can be ignored safely.\n * a monotonously-increasing queue can be maintained to save (presums[j] + last[j])\n *\n * Time Complexity: O(n)\n * Space Complexity: O(n)\n */\nclass Solution {\n public:\n  int findMaximumLength(const vector<int> &nums) {\n    const int n = static_cast<int>(nums.size());\n    long long presums[n];\n    memset(presums, 0, sizeof(presums));\n    for (long long presum = 0, i = 0; i < n; ++i) {\n      presum += nums[i];\n      presums[i] = presum;\n    }\n    \n    int dp[n];\n    memset(dp, 0, sizeof(dp));\n    long long last[n];\n    memset(last, 0, sizeof(last));\n    deque<int> dq;\n    dp[0] = 1;\n    last[0] = nums[0];\n    dq.emplace_back(0);\n    for (int i = 1; i < n; ++i) {\n      const long long presum = presums[i];\n      while (dq.size() > 1 &&\n             presum >= presums[dq[0]] + last[dq[0]] &&\n             presum >= presums[dq[1]] + last[dq[1]]) {\n        dq.pop_front();\n      }\n      if (presum >= presums[dq[0]] + last[dq[0]]) {\n        dp[i] = dp[dq[0]] + 1;\n        last[i] = presum - presums[dq[0]];\n      } else {\n        dp[i] = dp[i - 1];\n        last[i] = last[i - 1] + nums[i];\n      }\n      while (!dq.empty() && presums[dq.back()] + last[dq.back()] > presum + last[i]) {\n        dq.pop_back();\n      }\n      dq.emplace_back(i);\n    }\n    return dp[n - 1];\n  }\n};\n```
[]