For every index, we can calculate their prefix sum, which we can use to calculate the sums of subarrays of length k. From the 3 subarrays, for the middle subarray, we can do this:
The best subarray to the left of this middle subarray can be found using incrementally iterating through the numbers. The best subarray to the right of this middle subarray can be found using decrementally iterating through the numbers.
At the end, we can compare the total sums of sums of these first, middle and third subarrays for valid index and return the best indices.
Problem: https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/
Algorithm:
For every index, we can calculate their prefix sum, which we can use to calculate the sums of subarrays of length k. From the 3 subarrays, for the middle subarray, we can do this: The best subarray to the left of this middle subarray can be found using incrementally iterating through the numbers. The best subarray to the right of this middle subarray can be found using decrementally iterating through the numbers. At the end, we can compare the total sums of sums of these first, middle and third subarrays for valid index and return the best indices.