Prefix Count || O(n) || sliding window || with Image
Intuition\nSince we only need to choose two segement , why not consider one to left and one to right for all index \'i\'\n\n\n\n# Approach\nUsing sliding window
# Intuition\nSince we only need to choose two segement , why not consider one to left and one to right for all index \'i\'\n![IMG_0099.PNG](https://assets.leetcode.com/users/images/e3e30f91-e418-41a5-b66d-57fb1d72fd08_1675530398.6877542.png)\n\n\n# Approach\nUsing sliding window we can find the max count for [0,i] for all i we storre in prefix array,\nsimilarly if we can find for suffix array .\nThe max value of [0,i] + [i+1,n-1] is our answer\n\n\n# Complexity\n- Time complexity:\nO(n) -- sliding window\n\n- Space complexity:\nO(n) --  for prefix and suffix array\n\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& A, int k) {\n        int ans = 0,n = A.size();\n        //pointer to start of sliding window\n        int start = 0 ;\n        //variable for storing current count\n        int count = 0;\n        //end_limit of range\n        int end = A[0] + k;\n        \n        int cur_val = 0;\n        vector<int>pref(n),suff(n);\n\n        for(int i=0;i<n;++i){\n            int cur = A[i];\n            //if current element is in range we increment our count\n            if(cur<= end){\n                count++;\n            }\n            else{\n                //else we move the start of our window to right until current \n                //element is in range \n                while(cur>end){\n                    start++;\n                    end = A[start]+k;\n                    count--;\n                }\n                count++;\n            }\n            cur_val = max(cur_val,count);\n            //pref[i] -- it store the max count from [0,i]\n            pref[i] = cur_val;\n        }\n        \n        //now for suffix \n        start = n-1;\n        end = A[n-1] - k;\n        count = 0,cur_val = 0;\n\n        for(int i=n-1;i>=0;--i){\n            int cur = A[i];\n            //if current value is in range    \n            if(cur>=end){\n                count++;\n            }\n            else{\n                //else we move the start of our window to left until current \n                //element is in range (we are starting form end and moving to first so left movment)\n                while(cur<end){\n                    start--;\n                    end = A[start]-k;\n                    count--;\n                }\n                count++;\n                 \n            }\n            cur_val = max(cur_val,count);\n            //suff[i] --  it store the max count from [i,n-1]\n            suff[i] = cur_val;\n        }\n        \n        for(int i=0;i<n;++i){\n            int sum = pref[i];\n            if((i+1)<n)sum += suff[i+1];\n\n            //the max sum from [0,i] + [i+1,n-1]\n            ans = max(ans,sum);\n        }\n      \n        \n        return ans;\n    }\n};\n```\n
['Sliding Window', 'Prefix Sum', 'C++']