689. Maximum Sum of 3 Non-Overlapping Subarrays

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/
Constructs arrays ia, and ib:
ia[i] stores the beginning index of the largest sum with index <= i;
ib[i] stores the beginning index of the largest sum with index >= i;
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int nk = n-k+1;
        vector<int> s(nk, 0);
        for(int i=0; i<k; i++) s[0] += nums[i];
        for(int i=1; i<nk; i++) s[i] = s[i-1] + nums[i+k-1] - nums[i-1];
     
        vector<int> ia(nk, 0);
        ia[0] = 0;
        for(int i=1; i<nk; i++) {
            if(s[i]>s[ia[i-1]]) ia[i] = i;
            else ia[i] = ia[i-1];
        }
        vector<int> ic(nk, 0);
        ic[nk-1] = nk-1;
        for(int i=nk-2; i>=0; i--) {
            if(s[i]>=s[ic[i+1]]) ic[i] = i;
            else ic[i] = ic[i+1];
        }
        int best = 0;
        vector<int> res;
        for(int i=k; i<nk-k; i++) {
            int tmp = s[ia[i-k]] + s[i] + s[ic[i+k]];
            if(tmp>best) {
                best = tmp;
                res = {ia[i-k], i, ic[i+k]};
            }
        }
        return res;
    }