[Binary Search + DP - With TC & SC & Approach]
\n# Approach\n- Pick First_Range_STARTIdx from 0 till n-1\n- Now,START = prizePositions[START] , END = START + k\n- Find First_Range_ENDIdx Using Binary Search(
\n# Approach\n- Pick First_Range_STARTIdx from 0 till n-1\n- Now,START = prizePositions[START] , END = START + k\n- Find First_Range_ENDIdx Using Binary Search(END) or UpperBound(END) as all values in range [START,END] they are Now a part of First_Range\n- Now, Second_Range_STARTIdx will either start Just from First_Range_ENDIdx OR we will be skipping some and go till n to get maximum Second Range. This is Handled in **nextMaxRange Function** using takeIt OR notTake it LOGIC\n  1. Now, firstRange = First_Range_ENDIdx - First_Range_STARTIdx  \n  2. secondRange = nextMaxRange(First_Range_ENDIdx)\n- return max(ans,firstRange+secondRange)\n\n\n# Complexity\n- Time complexity:\n$$O(n*[logn + nextMaxRange])$$ \n= $$O(nlogn]$$\n*here, O[nextMaxRange] ~ logn  ,for particular idx ,So overall $$O(nlogn)$$\nBecause Using Memo, we will be going only Once in nextMaxRange Fn*\n\n\n- Space complexity:\n$$O(n)$$ , *memoized vector*\n\n# Code\n```\nclass Solution {\npublic:\n    int nextMaxRange(int idx,vector<int>& prizePositions,int k,int n,vector<int>& memo){\n        if(idx == n){\n            return 0;\n        }\n\n        if(memo[idx] != -1){\n            return memo[idx];\n        }\n\n        //not Take\n        int notTakeRange = 0 , takeRange = 0;\n        notTakeRange =  nextMaxRange(idx+1,prizePositions,k,n,memo);\n\n        //Take\n        int start = prizePositions[idx];\n        int end = start + k;\n        int endIdx = upper_bound(prizePositions.begin(),prizePositions.end(),end) - prizePositions.begin(); \n        takeRange = endIdx - idx;\n\n        return memo[idx] = max(takeRange,notTakeRange);\n\n    }\n    int maximizeWin(vector<int>& prizePositions, int k) {\n        int n = prizePositions.size();\n        vector<int> memo(n,-1);\n        int ans = 0;\n\n        for(int i=0;i<n;i++){\n            int start = prizePositions[i];\n            int end = start + k;\n            //just after Index of end\n            int endIdx = upper_bound(prizePositions.begin(),prizePositions.end(),end) - prizePositions.begin(); \n            int firstRange = endIdx - i;\n            int secondRange = nextMaxRange(endIdx,prizePositions,k,n,memo);\n           \n            ans = max(ans,firstRange+secondRange);\n\n        }\n\n        return ans;\n    }\n\n\n};\n```
['Binary Search', 'Dynamic Programming', 'C++']