Easy c++ solution 100% faster in binarySearch+dp
Intuition\n Describe your first thoughts on how to solve this problem. \nif use the the array then you find that it is sorted so we can apply binary search over
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nif use the the array then you find that it is sorted so we can apply binary search over here\n# Approach\n<!-- Describe your approach to solving the problem. -->\nbinary search and dynamic programing\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(nlogn)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& prize, int k) {\n        int n=prize.size();\n        \n        \n        vector<int> dp(n);\n        \n        for(int i=0;i<n;i++){\n            int lb=i;\n            int ub=n-1;\n            \n            while(lb<=ub){\n                int mid=(lb+ub)/2;\n                \n                if(prize[i]+k>=prize[mid]){\n                    dp[i]=(mid-i)+1;\n                    lb=mid+1;\n                }else{\n                    ub=mid-1;\n                }\n            }\n        }\n        int ans=0;\n        vector<int> maxArr(n);\n        int maxVal=dp[n-1];\n        for(int i=n-1;i>-1;i--){\n            maxVal=max(maxVal,dp[i]);\n            maxArr[i]=maxVal;\n        }\n        \n        for(int i=0;i<n;i++){\n            int next=dp[i]+i<n?maxArr[dp[i]+i]:0;\n            ans=max(ans,dp[i]+next);\n        }\n        return ans;\n    }\n};\n```
['C++']