Dynamic programming, Prefix Sum | C++ Solution | Optimised and explained well
Intuition\nThe solution uses dynamic programming to find the length of the maximum non-decreasing subarray. The key idea is to maintain a memo array that tracks
# Intuition\nThe solution uses dynamic programming to find the length of the maximum non-decreasing subarray. The key idea is to maintain a `memo` array that tracks the length and prefix sum of the non-decreasing subarray ending at each index.\n\n# Approach\n1. **Prefix Sum Calculation:**\n   ```c++\n   vector<long long> pref(n+1); // 1-indexed\n   pref[0] = 0;\n   for(int i = 0; i < n; i++) pref[i+1] = pref[i] + nums[i];\n   ```\n   This part creates a vector `pref` to store the prefix sums of the given `nums` array. It uses 1-based indexing for convenience. The loop calculates the prefix sums and stores them in the `pref` vector.\n\n2. **Dynamic Programming with Memoization:**\n   ```c++\n   vector<pair<int, long long>> memo(n+2);\n   memo[0].first = 1;\n   ```\n   This section initializes a vector `memo` to store pairs of values. The first value in each pair represents the length of the non-decreasing array, and the second value represents the prefix sum corresponding to that length. The vector is initialized with size `n+2` to accommodate possible indices.\n\n3. **Dynamic Programming Loop:**\n   ```c++\n   for(int i = 1; i <= n; i++){\n       memo[i] = max(memo[i], memo[i-1]);\n       int idx = lower_bound(pref.begin(), pref.end(), 2*pref[i] - memo[i].second) - pref.begin();\n       memo[idx] = max(memo[idx], {memo[i].first+1, pref[i]});\n   }\n   ```\n   This loop iterates over the `nums` array, and for each element at index `i`, it updates the `memo` array based on certain conditions. Let\'s break down the key parts:\n\n   - `memo[i] = max(memo[i], memo[i-1]);`: This updates the current entry in `memo` to be the maximum of its current value and the value from the previous index.\n\n   - `int idx = lower_bound(pref.begin(), pref.end(), 2*pref[i] - memo[i].second) - pref.begin();`: This line calculates the index where a certain condition is satisfied. It uses `lower_bound` to find the first element in `pref` whose value is greater than or equal to `2*pref[i] - memo[i].second`. This essentially looks for a prefix sum such that the sum of the current subarray and the sum of the previous subarray is doubled.\n\n   - `memo[idx] = max(memo[idx], {memo[i].first+1, pref[i]});`: This line updates the `memo` array at the calculated index `idx`. It sets the entry to be the maximum of its current value and a new pair `{memo[i].first+1, pref[i]}`, where the length of the non-decreasing subarray is incremented by 1, and the prefix sum is updated to the current prefix sum.\n\n4. **Return Result:**\n   ```c++\n   return memo[n].first;\n   ```\n   Finally, the function returns the length of the maximum non-decreasing subarray, which is stored in the last entry of the `memo` array.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n + n*log(n)) $$ ~ $$O(n*log(n))$$\n    * Prefix Sum Calculation: $$O(n)$$\n    * Dynamic Programming Loop:\n        - Outer loop iterates over each element in the nums array once, so $$O(n)$$.\n        - Inside the loop, lower_bound takes $$O(log(n))$$ time.\n        - Therefore, the overall time complexity of the loop is $$O(n*log(n))$$.\n\n- Space complexity:\n    * Prefix Sum Calculation: $$O(n + n)$$ ~ $$O(n)$$\n        - The space complexity is $$O(n)$$ for storing the pref vector.\n    * Dynamic Programming with Memoization:\n        - The space complexity is $$O(n)$$ for storing the memo vector.\n\n# Code\n``` C++ []\n// Original Author : @limbennett\nclass Solution {\npublic:    \n    int findMaximumLength(vector<int>& nums) {\n        int n = nums.size();\n        vector<long long> pref(n+1); // 1-indexed vector\n        pref[0] = 0;\n        for(int i = 0; i < n; i++) pref[i+1] = pref[i] + nums[i];\n        \n        vector<pair<int, long long>> memo(n+2);\n        memo[0].first = 1;\n        for(int i = 1; i <= n; i++){\n            memo[i] = max(memo[i], memo[i-1]);\n            int idx = lower_bound(pref.begin(), pref.end(), 2*pref[i] - memo[i].second) - pref.begin();\n            memo[idx] = max(memo[idx], {memo[i].first+1, pref[i]});\n        }\n        return memo[n].first;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'Prefix Sum', 'C++']