DP + Binary search O(N log N)
Intuition\nAssuming we\'re doing backtracking solution for this problem. Assuming we\'re at index i of nums, we\'re having an building array that satisfy the so
# Intuition\nAssuming we\'re doing backtracking solution for this problem. Assuming we\'re at index `i` of `nums`, we\'re having an building array that satisfy the solution requirements (non-decreased). Let call last element we have in our building array is `last_sum`. There are 2 cases:   \nCase 1: `nums[i] >= last_sum`, we just push `nums[i]` to our building array. \nCase 2: `nums[i] < last_sum`, we have 2 options: \n- 2.1: add `nums[i]` to `last_sum`, this will make our building array keeps being non-decreased. `last_sum` now will be `nums[i] + last_sum` \n- 2.2: we\'ll find the smallest `j` (`j > i`), such that:\n        `nums[i] + nums[i + 1] + ... + nums[j] >= last_sum` \nand will jump to j + 1, `last_sum` now will be `nums[i] + nums[i + 1] + ... + nums[j]`. \n\nIn case `2.2`, it\'s easy to see that there\'s no point to go further than `j` for now. Even if `nums[j + 1] + ... + nums.back()` <  `nums[i] + nums[i + 1] + ... + nums[j]`, we can go back to case 2.1 later when we\'re at `j+1`, it\'s not a problem to care when we\'re at `i`.\n\n# Approach\nBased on the backtracking solution, we\'ll go into the dp solution. Let `dp[i]` is the answer for the problem at index `i`. But we will keep another value indicates the minimum `last_sum` we can have. So our `dp[i]` is actually a pair of `{answer at i, last_sum}`.  Case `2.2` can be optimized with binary search + prefix sum. The solution is quite straight forward from the backtracking solution. \n\nYou may ask: "What if I have another solution at index `i` that have less elements, but my `last_sum` is smaller, so it can be optimized further?". My answer is there\'s no case like that :). It\'s not hard to prove it. \n\n# Complexity\n- Time complexity: $$O(n log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity $$O(n)$$:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int findMaximumLength(vector<int>& nums) {\n        const long long INF = 1e16 + 7; \n        vector<pair<int, long long> > dp(nums.size(), {0, INF});\n        vector<long long> pref(nums.size(), 0);\n        pref[0] = nums[0]; \n        for (int i = 1; i < nums.size(); i++) {\n            pref[i] = pref[i - 1] + nums[i]; \n        }\n        dp[0].first = 1;\n        dp[0].second = nums[0];\n        for (int i = 1; i < nums.size(); i++) {\n            if (nums[i] >= dp[i - 1].second) {\n                dp[i].first = max(dp[i - 1].first + 1, dp[i].first); \n                if (dp[i - 1].first + 1 == dp[i].first) {\n                    dp[i].second = min(dp[i].second, (long long)nums[i]);\n                }\n            } else {\n                dp[i].first = max(dp[i].first, dp[i - 1].first); \n                if (dp[i].first == dp[i - 1].first) {\n                    dp[i].second = min(dp[i].second, dp[i - 1].second + (long long)nums[i]);    \n                }\n            }\n            int lo = i; int hi = nums.size() - 1, idx = -1;\n            while (lo <= hi) {\n                int mi = (lo + hi) / 2; \n                if (pref[mi] - pref[i - 1] >= dp[i - 1].second) {\n                    idx = mi;\n                    hi = mi - 1; \n                } else {\n                    lo = mi + 1; \n                }\n            }\n            if (idx != -1) {\n                dp[idx].first = max(dp[idx].first, dp[i - 1].first + 1);\n                if (dp[idx].first == dp[i - 1].first + 1) {\n                    dp[idx].second = min(dp[idx].second, pref[idx] - pref[i - 1]);\n                }\n            }\n        }\n        return dp.back().first;\n    }\n};\n```
['C++']