💹Super Intuitive || O(nlog(n)) & O(n) solution explained || C++
Intuition\nIntuition : 1\nThe problem ask to cut the array in subarrays such that the sum of each subarrays is non-decreasing. So if we are standing at any inde
# Intuition\n**Intuition : 1**\nThe problem ask to cut the array in subarrays such that the sum of each subarrays is non-decreasing. So if we are standing at any index say i, we should be able to say how many subarrays can we get till ith index obeying problem constraints.\nAs we can always have a minimum answer of 1 at any index(0-i). We need to look how can we maximize our answer for ith index.\nMaximizing our answer for each index gives us a hint that our answer for ith index will always be >= (i-1)th index, as if answer for ith index comes to be smaller than (i-1)th index, we can always add ith element to subarray which has (i-1)th element and get our answer for ith index = answer for (i-1)th index.\n\n**Intuition : 2**\nSuppose we define dp[i] to be holding the best answer for ith index.\nlet\'s find out how can we get dp[i] for ith index.\nWe need to look for index j such that (0 <= j < i) and sum  nums[j+1]+nums[j+2]+...+nums[i] >= sum of subarray nums[ j ] is attached with(let\'s call it sumlast[ j ]).\nSo, we have:\n         prefixsum[ i ]-prefixsum[ j ] >= sumlast[ j ]\n         prefixsum[ i ]              >= sumlast[ j ] + prefixsum[ j ]\n\nwhat is sumlast[ i ]?\nIt is prefixsum[ i ]-prefixsum[ j ].\n\nWe can observe from it that for each index i, any index j(0 <= j < i) which satisfies the above condition for prefixsum[ i ] can be considered for calculating answer for dp[ i ].\ndp[ i ] = max(dp[ j ]+1)  for all j ( 0 <= j < i ).\n\n# Approach\nCalculate prefixsum of nums.\nInitialize a vector of pair ,say sk, first(prefix[index]+sumlast[index]), second(index).\nNow for every index i we can do a binary search for finding the index j which satisfy (sumlast[ j ]+prefixsum[ j ] <= prefixsum[ i ]) and is closest to i. \ndp[ i ]= dp[ j ]+1;\n\nPop out every element from sk till it has first >= prefixsum[ i ]+sumlast[ i ].\nPush prefixsum[ i ]+sumlast[ i ] to sk.\n\nThe final answer can be returned as dp[n].\n\nWe can further optimize our answer to O(n) using monotonic stack. To search for index j.\n\n# Complexity\n- Time complexity:\nO(nlog(n)) (Finding j using binary search).\nO(n) (using monotonic stack for finding j).\n\n# Code\n```\nclass Solution {\npublic:\n    //foxed-imp\n     \n    \n    int findMaximumLength(vector<int>& nums) {\n        \n        int n=nums.size();\n        vector<long long> v(n+1,0);\n        vector<int> dp(n+1,0);\n        \n        for(int i=1;i<=n; i++)\n            v[i]= v[i-1]+nums[i-1];\n        \n        \n        vector<vector<long long>> sk;\n        sk.push_back({0,0});\n        \n        for(int i=1; i<=n; i++)\n        {\n            int low=0, high=sk.size()-1;\n            int p=0;\n            \n            while(low<=high)\n            {\n                int mid= low+(high-low)/2;\n                \n                if(sk[mid][0]<= v[i])\n                {\n                    p= max(p,mid);\n                    low=mid+1;\n                }\n                else high=mid-1;\n            }\n            \n            int index= sk[p][1];\n            \n            dp[i]=dp[index]+1;\n            \n            long long add= 2*v[i]-v[index];\n            \n            while(sk.back()[0]>=add)\n                sk.pop_back();\n            \n            sk.push_back({add, i});\n    \n        }\n        \n        \n        return dp[n];\n    }\n};\n```
['Dynamic Programming', 'C++']