【LeetCode】689、三个无重叠子数组的最大和

一、dp

1.1 dp

// go
// 输入: nums[]
// 计算: 找三段长度为 k 的不重叠的子数组. 要求这 3k 个元素之和最大
// 输出: 三段子数组的 起始位置. 若有多个结果, 返回字典序最小的一个
func maxSumOfThreeSubarrays(nums []int, k int) []int {// 整体思路: 枚举 中间, 在左取长k的最大累加和子数组, 在右取长k的最大累加和子数组// 基础数据n := len(nums)sums := make([]int, n) // sums[i]: 起点为i, 长度为k, 的数组的累加和. 构造方式: 定长滑窗sum := 0 // 临时变量, 每一步的累加和for l, r := 0, 0; r < n; r++ {sum += nums[r]if r-l+1==k {sums[l] = sumsum -= nums[l]l++}}prefix := make([]int, n) // prefix[i]: [0..i]范围, 长k的 最大累加和 子数组, 的起始位置prefix[k-1] = 0 // 初始值l, r := 1, k // [l...r] 是长度为k的子数组for r < n {if sums[l] > sums[prefix[r-1]] { // 对应prefix[r-1]第一次遇到的值就是初始值prefix[r-1]// > 是为了同样最大累加和情况下, 最小的字典序prefix[r] = l} else {prefix[r] = prefix[r-1]}l++; r++}suffix := make([]int, n) // suffix[i]: [i..n-1]范围, 长k的 最大累加和 子数组, 的起始位置suffix[n-k] = n-k // 初始值for l := n-k-1; l >= 0; l-- {if sums[l] >= sums[suffix[l+1]] { // 对应suffix[l+1]第一次遇到的值就是初始值suffix[n-k]// >= 是为了同样最大累加和情况下, 最小的字典序suffix[l] = l} else {suffix[l] = suffix[l+1]}}// 枚举 中间, 在左右分别取 最大的. 选各情况中最大的// 0..i..j..n-1//  左  中  右i := kj := 2*k-1 // [i...j] 就是中间那个长度为k的子数组mx := 0 // 临时变量, 整体3k长度的 最大累加和a, b, c := 0, 0, 0 // 三个子数组的起点for j < n-k {// 0...i-1  i...j   j+1...n-1//  起点p    i开头     起点sp, s := prefix[i-1], suffix[j+1]sum := sums[p] + sums[i] + sums[s]if sum > mx {mx = suma, b, c = p, i, s}i++; j++}return []int{a, b, c}
}

【算法讲解071【必备】子数组最大累加和问题与扩展-下】

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts