689. Maximum Sum of 3 Non-Overlapping Subarrays
思路:
dp
用三个dp矩阵
dp1[i][0] : 表示到nums[i]为止长度k的subarray sum的最大值
dp1[i][1] : 为该subarray的起始index
dp2[i][0] : 表示到nums[i]为止2个长度为k且不重叠的subarray sum的最大值
dp2[i][1] : 为第1个subarray的起始index
dp2[i][2] : 为第2个subarray的起始index
dp3[i][0] : 表示到nums[i]为止3个长度为k且不重叠的subarray sum的最大值
dp3[i][1] : 为第1个subarray的起始index
dp3[i][2] : 为第2个subarray的起始index
dp3[i][3] : 为第3个subarray的起始index
dp1应该不用说明怎么求
dp2的话
假设sum为nums[i-k+1]~nums[i]的总和
那dp2的状态方程式为 dp2[i][0] = max(dp2[i-1][0] , sum+dp1[i-k] )
然后记得跟着更新dp2[i][1]、dp2[i][2]
dp3则是从dp2得到的，状态方程式跟dp2差不多
最后回传dp3[n-1][1:]就好
golang code :
func maxSumOfThreeSubarrays(nums []int, k int) []int {
n := len(nums)
dp1 := make([][2]int, n)
dp2 := make([][3]int, n)
sum := 0
for i := 0; i < k; i++ {
sum += nums[i]
}
dp1[k-1] = [2]int{sum, 0}
for i := k; i < n; i++ {
sum -= nums[i-k]
sum += nums[i]
if sum > dp1[i-1][0] {
dp1[i] = [2]int{sum, i - k + 1}
} else {
dp1[i] = [2]int{dp1[i-1][0], dp1[i-1][1]}
}
if sum+dp1[i-k][0] > dp2[i-1][0] {
dp2[i][0] = sum + dp1[i-k][0]
dp2[i][1] = dp1[i-k][1]
dp2[i][2] = i - k + 1
} else {
dp2[i] = dp2[i-1]
}
}
dp3 := make([][4]int, n)
sum = 0
for i := 2 * k; i < k; i++ {
sum += nums[i]
}
dp3[3*k-1] = [4]int{sum + dp2[2*k-1][0], dp2[2*k-1][1], dp2[2*k-1][2], 2 * k}
for i := 3 * k; i < n; i++ {
sum += nums[i]
sum -= nums[i-k]
if sum+dp2[i-k][0] > dp3[i-1][0] {
dp3[i] = [4]int{sum + dp2[i-k][0], dp2[i-k][1], dp2[i-k][2], i - k + 1}
} else {
dp3[i] = dp3[i-1]
}
}
return dp3[n-1][1:]
}