https://leetcode.com/contest/leetcode-weekly-contest-52/problems/maximum-sum-of-3-non-overlapping-subarrays/

[Implementation idea]:

[Native way]

A native way is to check all triple candidates, filter out illegals and find the one the maximum sum. Complexity is O(n^3).

[Better way]

Apply dynamic programming.
Complexity is O(nlogn)
Complexity is O(n)

Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Assume A(i, j) represents the maximum j Non-Overlapping Sub-arrays sum whose last chosen index is at position i.

A(i, 1) =
1. sum(A(k)) k = i, i-1, ... i-k+1, if i  >= (k - 1).
2. 0, otherwise.

A(i, 2) =
1. A(i, 1) + max(A(i-k, 1)); if i  >= (2*k - 1). 
2. 0, otherwise.

A(i, 3) =
1. A(i, 1) + max(A(i-k, 2)); if i  >= (3*k - 1). 
2. 0, otherwise.

Formula A(i,1) is intuitive;

Formula A(i,2) comes from the fact that - we must ended at i so A(i), A(i-1), ... A(i-k+1) are included which exactly are the result of A(i,1); then we need to select the other consecutive k with max sum from A(0), A(1), ... A(i - k) which are exactly the result of  max(A(i-k, 1)).

Formula A(i,3) comes from the fact that - we must ended at i so A(i), A(i-1), ... A(i-k+1) are included which exactly are the result of A(i,1); then we need to select the other TWO consecutive k with max sum from A(0), A(1), ... A(i - k) which are exactly the result of  max(A(i-k, 2)).

The complexity of A(i,1) is O(n).
The complexity of A(i,2) is O(nlogn).
The complexity of A(i,3) is O(nlogn).
A(i,2) & A(i,3) are implemented with a max queue.
The complexity of A(i,1) is O(n).
The complexity of A(i,2) is O(n) (maintain & update max only).
The complexity of A(i,3) is O(n) (maintain & update max only).

[Ex]:
For input 1, 2, 1, 2, 6, 7, 5, 1 and k = 2:
A(i, 1) is listed below:

A(i, 2) is listed below:

A(i, 3) is listed below:

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {

        vector<int> Answer(3, -1);
        if (k > (nums.size() / 3)) {
            return Answer;
        }

        vector<long long> A1(nums.size(), 0);
        vector<long long> A2(nums.size(), 0);
        vector<long long> A3(nums.size(), 0);

        vector<int> P2(nums.size(), -1);
        vector<int> P3(nums.size(), -1);

        int sum = 0;
        int i;

        for (i = 0; i < k; i++) {
            sum += nums[i];
        }
        i = k - 1;
        while(1) {
            A1[i] = sum;
            if (i < (nums.size() - 1)) {
                sum += nums[i + 1];
                sum -= nums[i - k + 1];
                i++;
            } else {
                break;
            }
        }

        int max = A1[k - 1];
        i = (2 * k) - 1;
        int pos = k - 1;
        while(1) {
            A2[i] = A1[i] + max;
            P2[i] = pos;
            /*update max*/
            if (i < (nums.size() - 1)) {
                i++;
                if (A1[i - k] > max) {
                    max = A1[i - k];
                pos = i - k;
                }
            } else {
                break;
            }
        }

        max = A2[(2 * k) - 1];
        i = (3 * k) - 1;
        pos = (2 * k) - 1;
        long long best = LLONG_MIN;
        int bestPosition = -1;
        while(1) {
            A3[i] = A1[i] + max;
            if (A3[i] > best) {
                best = A3[i];
                bestPosition = i;
            }
            P3[i] = pos;
            /*update max*/
            if (i < (nums.size() - 1)) {
                i++;
                if (A2[i - k] > max) {
                    max = A2[i - k];
                    pos = i - k;
                }
            } else {
                break;
            }
        }

        Answer[2] = (bestPosition - k + 1);
        Answer[1] =(P3[bestPosition]- k + 1);
        Answer[0] =(P2[P3[bestPosition]]- k + 1);

        for (i = 0; i < 3; i++) {
            printf("%-4d, ", Answer[i]);
        }
        cout << "\n";

        return Answer;
    }
};

int main()
{
    int myints[] = {1,2,1,2,6,7,5,1};
    vector<int> input(myints, myints + sizeof(myints) / sizeof(int) );

    Solution solution;
    solution.maxSumOfThreeSubarrays(input, 1);
    return 1;
}