C++ | | DP+BS | | Memoization | | Well Explained Code
Intuition\nWe will be going through all the possible combinations of windows and return the max sum.The code will be making sure that the windows don\'t overlap
# Intuition\nWe will be going through all the possible combinations of windows and return the max sum.The code will be making sure that the windows don\'t overlap.We will be traversing from right to left as it\'ll allow us to apply binary search to find the start of the window whose end is \'Arr[i]\'\n\n# Approach\n->Start traversing from right to left.\n->At each index make decisions to include the window that\'ll be formed here(End at Arr[i]) or not.\n->In case of exclusion we simply move to next index(i-1).\n->In case of inclusion we have to find the start of the window by binary search (lower bound of Arr[i]-k).The length of the window will be i-idx+1(idx is start of the window) and now to avoid overlapping we simply passs idx-1 to the next call and add the window length and decrement the X variable in next call(X variable denotes the number of windows selected so far)\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int Help(int i,int X,vector<int> &prizePositions,int k,vector<vector<int>> &dp)\n    {\n        if(X==0)//2 windows have been formed\n        {\n            return 0;\n        }\n        if(i<0)//Invalid case(2 windows weren\'t formed)\n        {\n            return INT_MIN;\n        }\n        if(dp[i][X]!=-1)\n        {\n            return dp[i][X];\n        }\n\n        int exc=Help(i-1,X,prizePositions,k,dp);//exclusion case\n        int inc;//inclusion case\n        int idx=lower_bound(prizePositions.begin(),prizePositions.end(),prizePositions[i]-k)-prizePositions.begin();//To find the start of this window\n        inc=(i-idx+1)+Help(idx-1,X-1,prizePositions,k,dp);\n\n        return dp[i][X]=max(inc,exc);\n    }\n\n    int maximizeWin(vector<int>& prizePositions, int k)\n    {\n        int n=prizePositions.size();\n        if(2*k>=prizePositions[n-1]-prizePositions[0])//If combined length is greater than the range we can cover all prizes\n        {\n            return n;\n        } \n        vector<vector<int>> dp(n+1,vector<int> (3,-1));\n        return Help(prizePositions.size()-1,2,prizePositions,k,dp);\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Memoization', 'C++']