Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nDP steps:\n1. Form 2 max ending here form: dp[i] = solution ending at i, last sum at i\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDP steps:\n1. Form 2 max ending here form: dp[i] = solution ending at i, last sum at i\n2. dp meaning: dp[i] = answer upto i. Since we can always merge i into i-1, dp[i][0] >= dp[i-1][0] so final answer will be dp[n-1][0]\n3. dp transition: at i, we have the following options:\n        - If nums[i] >= dp[i-1][1], \n        - candidate solution is: dp[i][0] = dp[i-1][0] + 1, dp[i][1] = nums[i]\n        - If nums[i] < dp[i-1][1], \n        - candidate solution is dp[i][0] = dp[i-1][0], dp[i][1] = dp[i-1][1] + nums[i]\n        - If nums[i] < dp[i-1][1], we can also look for j >= i such that pre[j] - pre[i-1] >= dp[i-1][1], (solve for j at i) to maximize the number of elements, we will look for the smallest such j. If nums[i] >= dp[i-1][1], this will just end up finding the answer from the first case, so we can do this at every turn regardless\n4. TC check: O(nlogn)\n5. Optimization: initial conditions: every element is 0, INF where INF is some large value. We want to maximize the first term and minimize the second term. Because any index can be filled with a candidate solution beforehand, we have to take max/min while trying to apply any of the candidate solutions\n\nRead: https://leetcode.com/problems/find-maximum-non-decreasing-array-length/solutions/4331411/dp-binary-search-o-n-log-n/\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int findMaximumLength(vector<int>& nums) {\n        int n = nums.size();\n        long long INF = 1e15;\n        vector<vector<long long>> dp(n, vector<long long>(2, 0));\n\n        for(int i = 0; i<n; i++)\n        {\n            dp[i][1] = INF;\n        }\n\n        dp[0][0] = 1;\n        dp[0][1] = nums[0];\n\n        vector<long long> pre(n, 0);\n        pre[0] = nums[0];\n\n        for(int i = 1; i<n; i++)\n        {\n            pre[i] = pre[i-1] + nums[i];\n        }\n\n\n        for(int i = 1; i<n; i++)\n        {\n\n            if(nums[i] >= dp[i-1][1])\n            {\n                dp[i][0] = max(dp[i-1][0] + 1, dp[i][0]);\n                if(dp[i][0] == dp[i-1][0] + 1) // we have improved the solution, so let the greatest element here be the min possible\n                {\n                    dp[i][1] = min(dp[i][1], (long long)nums[i]);\n                } \n            }\n            else\n            {\n                dp[i][0] = max(dp[i-1][0], dp[i][0]); // overwrite the answer here if it is less than what we can get by combining with i-1\n                if(dp[i][0] == dp[i-1][0])\n                {\n                    dp[i][1] = min(dp[i][1], (long long)nums[i] + dp[i-1][1]);\n                }\n            }\n\n\n            int hi = n-1;\n            int lo = i;\n            int ans = -1;\n\n            while(lo <= hi)\n            {\n                int mid = lo + (hi - lo)/2;\n                if(pre[mid] - pre[i-1] >= dp[i-1][1])\n                {\n                    ans = mid;\n                    hi = mid-1;\n                }\n                else\n                {\n                    lo = mid+1;\n                }\n            }\n\n            if(ans != -1)\n            {\n                dp[ans][0] = max(dp[ans][0], dp[i-1][0] + 1);\n                if(dp[ans][0] == dp[i-1][0] + 1)\n                {\n                    dp[ans][1] = min(dp[ans][1], pre[ans] - pre[i-1]);\n                }\n            }\n            \n        }\n        \n\n        return dp[n-1][0];\n    }\n};\n```
['C++']