[C++] Binary Search | DP | Beats 100% |  Easy + Intuitive Explanation | Illustration
\n# Solution\nWe Calculate the maximum number of prizes we can collect if we start collecting from index i , using binary search to find the first index that ca
\n# Solution\n**We Calculate the maximum number of prizes we can collect if we start collecting from index i , using binary search to find the first index that cannot be included if we start at index i.**\n\nAfter that we can just iterate over all index\'s **finding the maximum possible length of segment 1 , which was already calculated in the previous step (DP). For segment 2, we take the maximum possible value of all the remaning indices that remain after inclusion of segment 1 (stored in DP2 using suffix maximum).**\n\n**The answer is the maximum over all index\'s.**\n\n ![explainationleetcodee.png](https://assets.leetcode.com/users/images/2bd509d5-aee5-421d-aa8d-6f539a102ff4_1675550563.418666.png)\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& a, int k) {\n        int n = (int)a.size();\n        vector<int>dp(n,0);\n        for(int i = 0 ; i < n ; i++) {\n        //Calculates the maximum number of prizes we can collect if we start at index i.\n\n         int p = upper_bound(a.begin(),a.end(),a[i] + k) - a.begin(); // binary search to find the first index that cannot be included\n         int len = p - i; // length of the segment that can included we start at index i.\n         dp[i] = len; // storing the best possible answer if we start collecting prizes if we start at index i.\n        }      \n        vector<int>dp2 = dp;\n        int mx = dp[n-1];\n        for(int i = n-1 ; i >= 0 ; i--) {\n            mx = max(dp[i],mx);\n            dp2[i] = mx; // creating suffix maximum array.\n        }\n        int ans = 0;\n        for(int i = 0 ; i < n ; i++) {\n         int res = dp[i]; // gives the maximum number of prizes we can take if we start at index i [Segment 1]. (marked blue & red in picture)\n         if(i+dp[i] < n) {\n            // Maximum possible value for Segment 2 (marked as pink in picture)\n            res += dp2[i+dp[i]]; \n         }\n         ans = max(ans,res); // maximum possible answer.\n        }\n        return ans;\n    }\n};\n```
['Array', 'Binary Search', 'Dynamic Programming', 'C++']