【算法-动态规划】、魔法卷轴: 两次清零机会整个数组最大累加和

【算法-动态规划】、魔法卷轴: 两次清零机会整个数组最大累加和

一、dp

1.1 题意理解

nums 数组, 有正负0, 使用最多两次魔法卷轴, 希望使数组整体的累加和尽可能大. 求尽可能大的累加和
其实就是需要分情况讨论, 可能使用0/1/2个魔法卷轴
使用的效果: 把 nums 连续的一段全变为0

1.2 整体思路

分情况讨论:
0. 若使用0次魔法卷轴, 则答案即为 全数组的累加和

1. 若使用1次魔法卷轴, 对于 dp[i] 来说, 分为如下情况"要或不要":
   1.1 要 nums[i], 则 dp[i] = dp[i-1] + nums[i]. 因为要 nums[i] 则说明在 i 位置没有使用魔法卷轴, 而目标是必须使用1次魔法卷轴, 则必然在 dp[i-1] 即前 i-1 内用那1次魔法卷轴
   1.2 不要 nums[i], 说明 i 位置会使用魔法卷轴, 但魔法卷轴可以是一段区间而不是一个点, 所以需要看 从 i 位置向前到哪个位置(如i-1, i-2, …等) 都需使用魔法卷轴. 本质是哪个位置的前缀和最大, 则截止到哪. 例如若 presum[i-3] 最大, 则 i-2, i-1, i 都使用魔法卷轴即可.
2. 若使用2次魔法卷轴, 则对 i 来说, 在 nums[0…i-1] 用一次, 在 nums[i…n-1] 再用一次

1.3 具体思路

0. 用0次魔法卷轴, 求出整个数组的和
   求前缀和 presum[i] = sum(nums[0…i-1]), 求后缀和 sufsum[i] = sum(nums[i…n-1])
1. 用1次魔法卷轴, dp[i] 可根据 dp[i-1] 和 nums[i] 和 presum[i] 求出
2. 用2次魔法卷轴, dp[i] 可根据 presum[i] 和 sufsum[i] 求出

1.4 代码

package mainimport ("fmt""math""math/rand"
)func main() {fmt.Println("测试开始")n, v := 50, 10times := 10000for range times {sz := rand.Intn(n)nums := randArr(sz, v)a := f1(nums)b := f2(nums)if a != b {panic("匹配失败")}}fmt.Println("完全匹配成功")
}// dp
func f1(nums []int) int {n := len(nums)if n == 0 {return 0}// 用 0 次卷轴p0 := 0for _, v := range nums {p0 += v}// 基础数据// prefix[i] 表示从 0~i 范围内, 必须用 1 次卷轴, 0~i范围的最大累加和prefix := make([]int, n)prefix[0] = 0            // 0~0 范围内只有 nums[0] 一个数, 而且还用了卷轴, 所以整个数组的累加和肯定是 0sum := nums[0]           // 每一步的前缀和maxPresum := max(0, sum) // 各步 前缀和的最大值, 若整个数组都是负数, 则 maxPresum 应为 0for i := 1; i < n; i++ {prefix[i] = max(prefix[i-1]+nums[i], maxPresum) // 前者留 nums[i], 后者不留 nums[i]sum += nums[i]maxPresum = max(maxPresum, sum)}// 必须用 1 次卷轴p1 := prefix[n-1]// 基础数据// suffix[i] 表示从 i~n-1 范围内, 必须用 1 次卷轴, i~n-1范围的最大累加和suffix := make([]int, n)suffix[n-1] = 0         // n-1~n-1范围内只有 nums[n-1] 一个数, 而且还用了卷轴, 所以整个数组的累加和肯定是 0sum = nums[n-1]         // 每一步的前缀和maxPresum = max(0, sum) // 各步 前缀和的最大值, 若整个数组都是负数, 则 maxPresum 应为 0for i := n - 2; i >= 0; i-- {suffix[i] = max(suffix[i+1]+nums[i], maxPresum) // 前者留 nums[i], 后者不留 nums[i]sum += nums[i]maxPresum = max(maxPresum, sum)}// 必须用 2 次卷轴// 即遍历 i, 在 0~i-1范围内必须用 1 次, 在 i~n-1 范围内必须再用 1 次p2 := math.MinIntfor i := 1; i < n; i++ { // 注意, i 必须从 1 开始, 否则 0~i-1 范围是非法的p2 = max(p2, prefix[i-1]+suffix[i])}return max(p0, p1, p2)
}// 暴力法
func f2(nums []int) int {n := len(nums)p0 := 0for _, v := range nums {p0 += v}p1 := mustOneScroll(nums, 0, n-1)p2 := 0// 枚举划分点for i := range n {p2 = max(p2, mustOneScroll(nums, 0, i-1)+mustOneScroll(nums, i, n-1))}return max(p0, p1, p2)
}// 暴力辅助函数: 必须用 1 次卷轴
func mustOneScroll(nums []int, l, r int) int {ans := math.MinInt// 枚举划分点 l...a...b...r-1, 使 a...b 之间使用卷轴// 在 a...b 左比右闭区间使用卷轴for a := l; a <= r; a++ {for b := a; b <= r; b++ { // b 可能等于 a, 因为必须使用 1 次卷轴curAns := 0for i := l; i < a; i++ { // 不含 acurAns += nums[i]}for i := b + 1; i < r; i++ { // 不含 bcurAns += nums[i]}ans = max(ans, curAns)}}return ans
}func randArr(n, v int) []int {ans := make([]int, n)for i := range ans {ans[i] = rand.Intn(v)}return ans
}

参考代码

二、多语言解法

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

// cpp

// go 同上

# python

// rust

// js

// ts