# Leetcode 689 - Max sum of 3 non-overlapping subarrays

Note:

• How to find the max sum of 2 non-overlapping subs?
• Start from k, for the second array, keep tracking of the maxSum1.
• Because in every iteration the first array that contains maxSum1 must have appeared before the second array. We can be sure that they are not overlapping.
• How to find the max sum of 3 non-overlapping subs?
• Start from 2k, for the 3rd array, keep tracking maxSum1 and maxSum12.
• Because we’ve made sure that 1st and 2nd arrays won’t overlap, the 3rd array appears after them, so it won’t overlap either.
• An overlooked detail:
• maxSum1Index doesn’t necessarily equal to maxSum12Index. Because a num might be bigger than maxSum1, but num + sum2 < maxSum12. So maxSum12Index1 and maxSum12Index2 must be set only when maxSum1 + sum > maxSum12.

Question:

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Code:

Introduction: Max sum of 2 non-overlapping subarrays

Max sum of 3 non-overlapping subarrays