Maximum Sum of 3 Non-Overlapping Subarrays in C++

Suppose we have one array called nums of positive integers, we have to find three non-overlapping subarrays with maximum sum. Here each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

We have to find the result as a list of indices representing the starting position of each interval. If there are multiple answers, we will return the lexicographically smallest one.

So if the input is like [1,2,1,2,6,8,4,1] and k = 2, then the result will be [0,3,5], so subarrays are [1,2], [2,6], [8,4] correspond to the starting indices [0,3,5].

To solve this, we will follow these steps −

• n := size of nums
• Define an array ret of size 3 fill this with inf
• Define an array sum of size n + 1
• for initialize i := 0, when i <n, update (increase i by 1), do −
  • sum[i + 1] = sum[i] + nums[i]
• Define an array posLeft of size n
• Define an array posRight of size n fill this with n - k
• for initialize i := k, currMax := sum[k] - sum[0], when i < n, update (increase i by 1), do −
  • newTotal := sum[i + 1] - sum[i + 1 - k]
  • if newTotal > currMax, then −
    • currMax := newTotal
    • posLeft[i] := i + 1 - k
  • Otherwise
    • posLeft[i] := posLeft[i - 1]
• for initialize i := n - k - 1, currMax := sum[n] - sum[n - k], when i >= 0, update (decrease i by 1), do −
  • newTotal := sum[i + k] - sum[i]
  • if newTotal >= currMax, then −
    • currMax := newTotal
    • posRight[i] := i
  • Otherwise
    • posRight[i] := posRight[i + 1]
• req := 0
• for initialize i := k, when i <= n - 2 * k, update (increase i by 1), do −
  • l := posLeft[i - 1], r := posRight[i + k]
  • temp := (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r])
  • if temp > req, then −
    • ret[0] := l, ret[1] := i, ret[2] := r
    • req := temp
• return ret

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution { public:    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {       int n = nums.size();       vector <int> ret(3, INT_MAX);       vector <int> sum(n + 1);       for(int i = 0; i < n; i++){          sum[i + 1] = sum[i] + nums[i];       }       vector <int> posLeft(n);       vector <int> posRight(n, n - k);       for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){          int newTotal = sum[i + 1] - sum[i + 1- k];          if(newTotal > currMax){             currMax = newTotal;             posLeft[i] = i + 1 - k;          }else{             posLeft[i] = posLeft[i - 1];          }       }       for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){          int newTotal = sum[i + k] - sum[i];          if(newTotal >= currMax){             currMax = newTotal;             posRight[i] = i;          }else{             posRight[i] = posRight[i + 1];          }       }       int req = 0;       for(int i = k; i <= n - 2 * k; i++){          int l = posLeft[i - 1];          int r = posRight[i + k];          int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);          if(temp > req){             ret[0] = l;             ret[1] = i;             ret[2] = r;             req = temp;          }       }       return ret;    } }; main(){    Solution ob;    vector<int> v = {1,2,1,2,6,8,4,1};    print_vector(ob.maxSumOfThreeSubarrays(v, 2)); }

Input

{1,2,1,2,6,8,4,1} 2

Output

[0, 3, 5, ]