C++ || Binary Search || Lower bound || Suffix Max
Complexity\n- Time complexity: O(NlogN+N+N)\n\n- Space complexity: O(3N)\n\n# Code\n\nclass Solution {\npublic:\n\n    //find last value of val\n    //1 2 2  3 
# Complexity\n- Time complexity: O(NlogN+N+N)\n\n- Space complexity: O(3N)\n\n# Code\n```\nclass Solution {\npublic:\n\n    //find last value of val\n    //1 2 2  3 4 5\n    //2 3 3  4 5 5\n    int lowerBound(vector<int>& nums, int &ws,int &n, int lo , int hi, int val){\n        int j = -1;\n        while(lo<=hi){\n            int mid = lo+(hi-lo)/2;\n\n            if( nums[mid] <= val ){\n                lo = mid+1;\n                j = mid;\n            }\n            else{\n                hi = mid-1;\n            }\n        }\n\n        if(j == -1){\n            return n-1;\n        }\n        return j;\n    }\n    int maximizeWin(vector<int>& nums, int k) {\n        int n = nums.size();\n\n        int ws = k;\n        vector<pair<int,int>> endidx(n);//{endIdx,max no.of prices}\n        for(int i=0;i<n;i++){\n            int val = nums[i]+k;\n            int j = lowerBound(nums,ws,n,0,n-1,val);\n            endidx[i].first = j;\n            endidx[i].second = j-i+1;\n        }\n\n\n        vector<int> suffixMax(n);\n        for(int i=n-1;i>=0;i--){\n            if(i == n-1){\n                suffixMax[n-1] = endidx[n-1].second;\n            }\n            else{\n                suffixMax[i] = max(suffixMax[i+1],endidx[i].second);\n            }\n        }\n\n        \n        int ans = 0;\n        for(int i=0;i<n;i++){\n            int j = endidx[i].first;\n            // int t = endidx[i].second + (i==n-1? 0: suffixMax[j+1]);\n            int t;\n            \n            if(j == n-1){\n                t = endidx[i].second;\n            }\n            else{\n                t = endidx[i].second + suffixMax[j+1];\n            }\n            ans = max(ans,t);\n        }\n\n        return ans;\n\n    }\n};\n\n```
['Binary Search', 'C++']