Dynamic Programming C++ solution with Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first idea was to use Dynamic Programming with two states namely, the current index
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first idea was to use Dynamic Programming with two states namely, the current index and the last element which is created after optimal merging of the array elements till the current index `dp(i, lastSum)`. The return value would be the maximum number of elements in the optimal merging till the ith element with the last element in the resulting array being <= lastSum. \n\nThe transition would have been (`MAX_SUM` represents that sum of all the elements in the array).\n\n\n```c++ []\nfor (int j = i-1 ; j >= 0 ; j--) {\n    for (int lastSum = 0 ; lastSum < MAX_SUM ; lastSum++)    \n        dp[i][lastSum] = max(dp[i][lastSum], dp[j][lastSum] + 1)\n}\n\nfor (int sum = 1 ; sum < MAX_SUM ; sum++) {\n    dp[i][sum] = max(dp[i][sum], dp[i][sum-1]);\n}\n```\n\nThis solution however is really slow, so let\'s try to optimize this dp `dp(i, lastSum)`. On close observation we notice two things:\n\n- The second state `lastSum` is constant in the resulting transition. So can we skip it? Let\'s see. Notice that when lastSum (in the state) increased `dp(i, lastSum)` decreased. So we can maintain a new `dp(i) = pair of (max number of elements till ith index, the minimum last element in the optimal array)`. Why is this reasonable to do? This is because the two states we originally came up with are inversely proportional (i.e., for greater `i` the answer would be greater but for greater `lastSum` the answer will be smaller). If those states would have been independent then we wouldn\'t have been able to do this optimization.\n- The answer for a particular index (i.e., the maximum number of elements in the optimally merged array till the current index) is always >= the answer for the previous index since we can simply merge the current element to the last element in the resulting optimal array for the previous index. So we conclude there is only a specific transition needed for each index.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nLet\'s try a naive implementation of our approach we discussed above.\n\n```c++ []\n\nvector<pair<int,int>> dp(n+1);\ndp[0] = {0, 0};\n\nfor (int i = 1 ; i <= n ; i++) {\n    int currSum = nums[i-1];\n    for (int j = i-1 ; j >= 0 ; j--) {\n        if (dp[j].second <= currSum) {\n            dp[i] = {dp[j]+1, currSum};\n            break;\n        }\n    }\n}\n```\n\nThis is however still very slow. Let\'s see how we can optimize it. Let\'s say we create a prefix array on nums. Let\'s call it `pref`.\n\nSo we notice\n```\ncurrSum = pref[i] - pref[j];\ncurrSum >= dp[j].second ==> pref[i] - pref[j] >= dp[j].second\n==> pref[i] >= dp[j].second + pref[j]\n```\n\nSo let\'s say we create a new array `cumSum` where\n```\ncumSum[i] = pref[i] + dp[i].second;\n```\nthen we can say the condition for fetching the appropriate j for the ith index is\n```\npref[i] >= cumSum[j]\n```\n\nIf cumSum was monotonic then we could have simply binary searched for the appropriate j. However turns out cumSum is not monotonic so binary search isn\'t possible. Or is it? Let\'s see.\n\nLet\'s say we have two index `j, k` in our cumSum array where `j < k and cumSum(j) > cumSum(k)`. Since `pref(j) < pref(k)` (since all elements of nums are positive), we can say `dp(j).second > dp(k).second`. Now we also say that `dp(j).first < dp(k).first (since for all x < y dp(x).first < dp(y).first)`. Thus it woud **never** be optimal to have use the jth index over kth index for any index `i > max(j,k)`. Thus before inserting k\'s contribution in cumSum we can remove all such `j` from the cumSum array. Since we\'ll be doing everytime it is evident that the current cumSum would be monotonic so the only removals are to be done from the back of the vector. Thus now we can ensure that cumSum will always be monotonic and hence use binary search for our answer. \n\nPlease note in the implementation:\ndp(i).first --> dp(i)\ndp(i).second --> last(i)\n\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\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        int n = nums.size();\n        vector<long long> dp(n+1), last(n+1);\n\n        vector<long long> pref(n+1);\n        vector<pair<long long,int>> cumSum;\n        for (int i = 1 ; i <= n ; i++) {\n            pref[i] = pref[i-1] + nums[i-1];\n        }\n\n        cumSum.push_back({0, 0});\n        for (int i = 1 ; i <= n ; i++) {\n            auto it = lower_bound(cumSum.begin(), cumSum.end(), make_pair(pref[i], n+1)) - cumSum.begin();\n            it--;\n            \n            it = cumSum[it].second;\n            dp[i] = dp[it] + 1;\n            last[i] = pref[i] - pref[it];\n            long long curr = pref[i] + last[i];\n            while (cumSum.back().first > curr) {\n                cumSum.pop_back();\n            }\n            cumSum.push_back({curr, i});\n        }\n\n        return dp[n];\n    }\n};\n```
['Binary Search', 'Prefix Sum', 'C++']