Re: [閒聊] 每日leetcode
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:]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.17 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1735405750.A.57A.html
推
12/29 10:17,
11月前
, 1F
12/29 10:17, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1227 之 1554 篇)：