Calcualte all right segment win of every position (C++, O(n))
Intuition\nit must be a O(n) complexity\n\n# Approach\nfirstly find out all the max win in the right side of index i (choose a segment in right),\n\nand then it
# Intuition\nit must be a O(n) complexity\n\n# Approach\nfirstly find out all the max win in the right side of index i (choose a segment in right),\n\nand then iterate all left segment, find out the max of total win (left side + right side which already calculated as above)\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& prizes, int k) {\n     int n=int(prizes.size());\n\n     //1. calcualte all max win of right segment for each index\n     int winTotalRight=0,maxWinRight=0;\n     vector<int>maxWinRights(n,0);\n\n     for(int i=n-1,j=n-1;i>=0;) {\n        if(prizes[j]-prizes[i]<=k) {\n            winTotalRight++;\n            maxWinRight= max(maxWinRight,winTotalRight);\n            maxWinRights[i]=maxWinRight;\n            --i;\n        }\n        else {\n            j--;\n            winTotalRight--;\n            maxWinRights[i]=maxWinRight;\n        }\n     }\n\n     // find out max total win (left side + right side (already calcualted above))\n     int winTotalLeft=0,maxWinTotal=0;\n     for(int i=0,j=0;i<n;) {\n        if(prizes[i]-prizes[j]<=k) {\n            winTotalLeft++;\n            maxWinTotal = max(maxWinTotal,winTotalLeft+( (i<n-1)?maxWinRights[i+1]:0));\n            ++i;\n        }\n        else {\n            winTotalLeft--;\n            j++;\n        }\n     }\n\n     return maxWinTotal;\n    }\n};\n```
['C++']