Dp based C++
Intuition\nGreedy idea wont work here.\n\n# Approach\nWe will be using dynamic programming here. dp[i] will tell us about the most number of increasing subarray
# Intuition\nGreedy idea wont work here.\n\n# Approach\nWe will be using dynamic programming here. dp[i] will tell us about the most number of increasing subarrays we can divide the array till index i into. We will also maintain the minimum possible sum of the last subarray.\n\nThere are transitions mainly. One is the transition where we close the current subarray and start considering for a new subarray. For such cases we use binary search to find the smallest index where we can end the current subarray.\nThe second transition is where we add the current element to the existing subarray.\n\n# Complexity\n- Time complexity:\n$$O(n*log(n))$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int findMaximumLength(vector<int>& nums) {\n        int n=nums.size();\n        \n       vector<long long> pre(n+1);\n        for(int i=1;i<=n;i++)\n            pre[i]=pre[i-1]+nums[i-1];\n        \n        vector< pair<int,long long> > dp(n+1);\n        for(int i=0;i<=n;i++)\n            dp[i]={0,1e18};\n        \n        dp[0]={0,0};\n        for(int i=1;i<=n;i++)\n        {\n            long long prevSum=dp[i-1].second;\n            long long needed=pre[i-1]+prevSum;\n            \n            int low=i;\n            int high=n;\n            int where=-1;\n            while(low<=high)\n            {\n                int mid=(low+high)/2;\n                \n                if(pre[mid]>=needed)\n                {\n                    where=mid;\n                    high=mid-1;\n                }\n                else\n                    low=mid+1;\n            }\n            if(where!=-1)\n            {\n                pair<int,long long> p={dp[i-1].first+1,pre[where]-pre[i-1]};\n                \n                if(dp[where].first < dp[i-1].first+1 )\n                    dp[where]=p;\n                else if(dp[where].first==dp[i-1].first+1)\n                    dp[where].second=std::min(dp[where].second,pre[where]-pre[i-1]);\n            }\n            \n            if(dp[i].first < dp[i-1].first )\n                    dp[i]={dp[i-1].first,dp[i-1].second+pre[i]-pre[i-1]};\n            else if(dp[i].first==dp[i-1].first)\n                 dp[i].second=std::min(dp[i].second,pre[i]-pre[i-1]+dp[i-1].second);\n        }\n\n        int ans=0;\n        for(auto &[len,su] : dp)\n            ans=std::max(ans,len);\n        \n        return ans;\n    }\n};\n```
['C++']