Clean prefix solution || C++
Approach\nCode size is huge but not logic is\n- Left array : At every index find no. of prizes in a window of k (idx to left)\n- Right array : At every index fi
# Approach\nCode size is huge but not logic is\n- Left array : At every index find no. of prizes in a window of k (idx to left)\n- Right array : At every index find no. of prizes in a window of k (idx to right)\n- prefix array : keep track of maximum no. of prize till this point from right\n- Last for loop : at every index take the no. of prizes from left array and take the just next index of prefix array as we are storing maximum in prefix array\n\n# Complexity\n- Time complexity: O(N)\n- Space complexity: O(4N)\n\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& arr, int k) {\n        vector<pair<int,int>> vp;\n        for(int i=0;i<arr.size();){\n            int j = i;\n            while(j < arr.size() and arr[j] == arr[i]) j++;\n            vp.push_back({arr[i],j-i});\n            i = j;\n        }\n        int i=0,j=0,sum=0;\n        vector<int> left;\n        while(j < vp.size()){\n            int diff = vp[j].first - vp[i].first;\n            sum += vp[j].second;\n            if(diff <= k){\n                left.push_back(sum);\n            }else{\n                while(i <= j){\n                    sum -= vp[i].second;\n                    int diff = vp[j].first - vp[++i].first;\n                    if(diff <= k){\n                        left.push_back(sum); break;\n                    }\n                }\n            }\n            j++;\n        }\n        i=vp.size()-1,j=vp.size()-1,sum=0;\n        vector<int> right;\n        while(j >= 0){\n            int diff = vp[i].first - vp[j].first;\n            sum += vp[j].second;\n            if(diff <= k){\n                right.push_back(sum);\n            }else{\n                while(i >= j){\n                    sum -= vp[i].second;\n                    int diff = vp[--i].first - vp[j].first;\n                    if(diff <= k){\n                        right.push_back(sum); break;\n                    }\n                }\n            }\n            j--;\n        }        \n        reverse(right.begin(),right.end());\n        vector<int> pref(left.size());\n        int maxi = right.back();\n        for(int i=right.size()-1;i>=0;i--){\n            maxi = max(maxi,right[i]);\n            pref[i] = maxi;\n        }\n        int ans = 0;\n        for(int i=0;i<left.size();i++){\n            ans = max(ans,left[i]+(i+1 < left.size() ? pref[i+1] : 0));\n        }\n        return ans;\n    }\n};\n```
['C++']