very easy and intuitive|| fully explained
Intuition\n Describe your first thoughts on how to solve this problem. \nsee my first intuition was that , in none of the cases it is ideal for me to take two o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nsee my first intuition was that , in none of the cases it is ideal for me to take two overlapping subarrays , if it is possible for me to take two non overlapping subarrays than that would always be better.\nThere is just one case where you need to take overlapping subarrays that is when the number of position on x axis is less than 2*k here you can get all the rewards possible .\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nNow this question becomes same as dividing array in two k sized non overlapping subarrays and maximizing our sum , there is just one issue that we can\'t make our right and left dp on positions as it is 10^9 . hence what we will do is we will make dp on the unique pos present in our initial array, that would be in worst case be 10^5,\nnow we just need to take a sliding window approach to fill in these dp\'s and than we can iterate these dp\'s to find our answer.\n\nThere could be two cases on each pos-:\n1) left_max till pos(i)+right_max till pos(i+1);\n2) right_max till pos(i)+left_max till pos(i-1);\nmax of these value should be comapred to our gloabal answer.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\no(N) (i.e actually o(2*N));\n\n# Code\n```\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& arr, int k) {\n        map<int,int> mp;\n        vector<int> vec;\n        for(int i=0;i<arr.size();i++){\n            mp[arr[i]]+=1;\n            if(mp[arr[i]]==1){\n                vec.push_back(arr[i]);\n            }\n        }\n        \n        vector<int> left_max(vec.size(),0);\n        int left_max_val=mp[vec[0]];\n        int start=0;\n        int end=1;\n        int sum=mp[vec[0]];\n        left_max[0]=mp[vec[0]];\n        while(end<vec.size()){\n            while(end<vec.size() &&(vec[end]-vec[start])<=k){\n                sum+=mp[vec[end]];\n                left_max_val=max(sum,left_max_val);\n                left_max[end]=left_max_val;\n                end++;\n            }\n            while(end<vec.size() && start<=end && (vec[end]-vec[start])>k){\n                sum-=mp[vec[start]];\n                start++;\n            }\n        }\n        /*for(int i=0;i<vec.size();i++){\n            cout<<left_max[i]<<" ";\n        }*/\n       \n        vector<int> right_max(vec.size(),0);\n        int right_max_val=mp[vec[vec.size()-1]];\n        start=vec.size()-1;\n        end=vec.size()-2;\n        sum=mp[vec[vec.size()-1]];\n        right_max[vec.size()-1]=mp[vec[vec.size()-1]];\n        while(end>=0){\n            while(end>=0 &&(vec[start]-vec[end])<=k){\n                sum+=mp[vec[end]];\n                right_max_val=max(sum,right_max_val);\n                right_max[end]=right_max_val;\n                end--;\n            }\n            while(end>=0 && start>=end && (vec[start]-vec[end])>k){\n                sum-=mp[vec[start]];\n                start--;\n            }\n        }\n        /*for(int i=0;i<vec.size();i++){\n            cout<<right_max[i]<<" ";\n        }*/\n        int ans=INT_MIN;\n        for(int i=0;i<vec.size();i++){\n            int val=0;\n            if(i==0){\n                if(i+1<vec.size()){\n                    val=max(right_max[i],left_max[i]+right_max[i+1]);\n                }\n                else{\n                    val=max(right_max[i],left_max[i]);\n                }\n            }\n            else if(i==vec.size()-1){\n                if(i-1>=0){\n                    val=max(left_max[i],right_max[i]+left_max[i-1]);\n                }\n                else{\n                    val=max(left_max[i],right_max[i]);\n                }\n            }\n            else{\n                val=max(left_max[i]+right_max[i+1],right_max[i]+left_max[i-1]);\n            }\n            ans=max(ans,val);\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Sliding Window', 'C++']