Readme

689.Maximum-Sum-of-3-Non-Overlapping-Subarrays

这道题可以用动态规划很方便地求解最大值，但是如果要记录最大值所对应的区间的位置，则会略显麻烦。

考虑到本题恰好只求三段区间，所以很容易想到three-pass的套路。我们在数组里遍历一段长度为k的滑窗作为中间的区间，假设范围是[i:i+k-1]，那么我们只需要求在[0:i-1]内最大的长度为k的区间，以及在[i+k:n-1]内最大的长度为k的区间。这两个分量都是可以提前计算好的。我们只要在数组上从前往后跑一遍长度为k的滑窗，就可以记录任意前缀里曾经出现过的最大值，记做leftMax[i]；同理，在数组上从后往前跑一遍长度为k的滑窗，就可以记录任意后缀里曾经出现过的最大值，记做rightMax[i]。所以我们只要找到全局最大的leftMax[i-1] + sum[i:i+k-1] + rightMax[i+k]即可。

除此之外，我们还需要记录下leftMax[i]所对应的最大滑窗的位置，即为leftIdx[i]。这里要注意一个细节，因为题意要求，如果有多个总和相同的解，取index位置最小的解。所以我们从左往右遍历的时候，只有在leftMax大于历史最大值的时候才更新leftIdx，这样在相同的leftMax的时候我们保留的是较小的index。同理，我们在从右往左遍历的时候，当rightMax大于等于历史最大值，就可以更新rightIdx，这样在相同的rightMax的时候我们保留的是较小的index。