You can see my solution at ....

Max[i].val is Max value of (Sum x[b]->x[b+k-1]) | if b in [i,n]. And Max[i].ind will be minimum index with this optimal Sum.

Using this you can remove second loop to find optimal b index in brute force solution. (Because if you selected index a, index b will be from [a+k] to [n])

The idea is same as editorial solution.

You can do that:

1. Build the cumulative sum of the array (t[])

2. Go from left to right. Store in dpleft[i] the amount in the interval i, i-k. (dpleft[i] = t[i] — t[i-k])

3. Go from right to left. Store in dpright[i] the amount in the interval i, i+k. (dpright = t[i+k] — t[i])

4. Build the indexes in index left[] and index right[] and initialize with i (left) and n — i (right).

5. Go from k to n-k. If dpleft[i] > dpleft[i-1] then update indexleft[i] with i-k+1 (It means the max sum of any interval k that finishes at i from left to right, starts at position i-k+1) else update indexleft[i] with the max we have in indexleft[i-1] and update dpleft[i] with dpleft[i-1] (The previous position has the max value starting from 1 for any k interval)

6. Do the same now from right to left.

7. Go from k to n-k and take the max value of dpleft[i] + dpright[i]

This is my Solution.