Maximize (left max + right max) for every i || precomputations || O(n)
Intuition\nThe idea is that as we have to select two segments and making those segments disjoint would always be better. So lets take an index i in the array an
# Intuition\nThe idea is that as we have to select two segments and making those segments disjoint would always be better. So lets take an index i in the array and take the first segment in the left of i and the second segment in the right of i. \n\n# Approach\nMaximizing the (**left segment** + **right segments**) value over all indexes will give us the answer.\nWe can precompute the prefix and suffix array which stores the maximum prizes we can take from the left and right of some index.\n\n# Complexity\n- Time complexity: O(n)\nO(n) for precomputation + O(n) for calculating final answer\n\n# Code\n```\n#define ll int\nclass Solution {\npublic:\n    int maximizeWin(vector<int>& v, int k) {\n        ll n = v.size();\n        if(n == 1) return 1;\n        vector<ll> pre(n), suff(n);\n        ll s = 0;\n        for(ll i = 0; i < n; i++){\n            while(v[i] - v[s] > k){\n                s++;\n            }\n            ll len = i - s + 1;\n            ll prev = (i > 0) ? pre[i-1] : 0;\n            pre[i] = max(prev, len);\n        }\n        s = n-1;\n        for(ll i = n-1; i >= 0; i--){\n            while(v[s] - v[i] > k){\n                s--;\n            }\n            ll len = s - i + 1;\n            ll nx = (i < n-1) ? suff[i + 1] : 0;\n            suff[i] = max(nx, len);\n        }\n        ll ans = 0;\n        for(ll i = 0; i < n-1; i++){\n            ans = max(ans, pre[i] + suff[i + 1]);\n        }\n        return ans;\n\n    }\n};\n```
['Sliding Window', 'C++']