053.子数组最大累加和问题与扩展-下

前置知识：对数器、构建前缀信息的技巧、单调队列（一定要掌握，本节课 题目6 需要，后续讲“多重背包的单调队列优化”也需要）、子数组最大累加和问题与扩展-上

本节课是 上节 课内容的继续，见识更多与累加和相关的题目

而且有 4 个题来自真实大厂笔试题，都提供了对数器的验证代码来确保正确

很多解法的思路非常巧妙

题目1.乘积最大子数组 §

题目描述 §

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

提示：

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
• nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

测试链接 §

152.乘积最大子数组

思路 §

• max[i]：以 nums[i] 结尾，向左扩，乘积的最大值
• min[i]：以 nums[i] 结尾，向左扩，乘积的最小值

max[i] 和 min[i] 有三种情况：

1. 只要当前值，不往左扩，即：nums[i]
2. 要当前值，要往左扩，因为要连续，所以是：max[i-1] * nums[i]
3. 如果 nums[i] 是负数，min[i-1] 也是负数，乘起来就是最大值了，即：min[i-1] * nums[i]

答案是 max dp 表中的最大值

答案 §

乘积最大子数组

说明 §

题目中虽然给定的是 int 类型的数组，但是该方法是 int、double 类型的数组都能正确的做法

题目2.子序列累加和必须被 7 整除的最大累加和 §

题目描述 §

给定一个非负数组 nums，可以任意选择数字组成子序列，但是子序列的累加和必须被 7 整除

返回最大累加和

测试链接 §

对数器验证

思路 §

dp[i][j]：nums 前 i 个数形成的子序列一定要做到子序列累加和 %7 == j，这样的子序列最大累加和是多少

状态转移：

1. 不使用 nums[i-1]，即：dp[i-1][j]
2. 使用 nums[i-1]，即：dp[i-1][need]+nums[i-1]

i 只依赖 i-1，从 i=0 往上推即可

初始化：dp[0][*]，第 0 行表示 nums 为空，模数为 0 答案就是 0，否则是 -1，表示不存在这样的子序列

答案 §

package main
 
import (
	"fmt"
	"math/rand"
)
 
const (
	MOD = 7
)
 
// 动态规划
func maxSum1(nums []int) int {
	n := len(nums)
	// dp[i][j]: nums[0:i]
	// nums 前 i 个数形成的子序列一定要做到，子序列累加和 %7 == j
	// 这样的子序列最大累加和是多少
	// 其中: dp[i][j] == -1 代表不存在这样的子序列
	dp := make([][MOD]int, n+1)
	// 初始化：第 0 行表示 nums 为空
	dp[0][0] = 0
	for j := 1; j < MOD; j++ {
		dp[0][j] = -1
	}
 
	for i := 1; i <= n; i++ {
		num := nums[i-1]
		cur := num % MOD
		for j := 0; j < MOD; j++ {
			dp[i][j] = dp[i-1][j]
			need := (7 + j - cur) % 7
			// 或者写条件转移
			// need := 0
			// if cur <= j {
			// 	need = j - cur
			// } else {
			// 	need = j - cur + 7
			// }
			if dp[i-1][need] != -1 {
				dp[i][j] = max(dp[i][j], dp[i-1][need]+num)
			}
		}
	}
 
	return dp[n][0]
}
 
// 空间压缩
func maxSum2(nums []int) int {
	n := len(nums)
	dp0 := [MOD]int{}
	dp1 := [MOD]int{}
	// 初始化：第 0 行表示 nums 为空
	dp0[0] = 0
	for j := 1; j < MOD; j++ {
		dp0[j] = -1
	}
 
	for i := 1; i <= n; i++ {
		num := nums[i-1]
		cur := num % MOD
		for j := 0; j < MOD; j++ {
			dp1[j] = dp0[j]
			// need := (7 + j - cur) % 7
			// 或者写条件转移
			need := 0
			if cur <= j {
				need = j - cur
			} else {
				need = j - cur + 7
			}
			if dp0[need] != -1 {
				dp1[j] = max(dp1[j], dp0[need]+num)
			}
		}
		dp0, dp1 = dp1, dp0
	}
 
	return dp0[0]
}
 
// 暴力递归
func maxSum3(nums []int) int {
	// nums 形成的所有子序列的累加和都求出来
	// 其中 %7==0 的那些累加和中，返回最大的
	// 就是如下 f 函数的功能
	return f(nums, 0, 0)
}
 
// i: 当前遍历到的 nums 索引
// s: 当前累加和
func f(nums []int, i, s int) int {
	if i == len(nums) {
		if s%MOD == 0 {
			return s
		}
		return 0
	}
	return max(
		f(nums, i+1, s),         // 不要 nums[i]
		f(nums, i+1, s+nums[i]), // 要 nums[i]
	)
}
 
const (
	MAXN       = 15
	MAXV       = 30
	TEST_TIMES = 20000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		arr := randomArray()
		ans1 := maxSum1(arr)
		ans2 := maxSum2(arr)
		ans3 := maxSum3(arr)
		if ans1 != ans2 || ans1 != ans3 {
			panic("error")
		}
	}
	fmt.Println("ok")
}
 
func randomArray() []int {
	arr := make([]int, rand.Intn(MAXN)+1)
	for i := range arr {
		arr[i] = rand.Intn(MAXV)
	}
	return arr
}

复杂度 §

• 时间复杂度：$O(n)$
  • MOD = 7 复杂度可忽略
• 空间复杂度：
  • 动态规划：$O(n)$
  • 空间压缩：$O(1)$

题目3.魔法卷轴 §

题目描述 §

给定一个数组 nums，其中可能有正、负、0

每个魔法卷轴可以把 nums 中连续的一段全变成 0

你希望数组整体的累加和尽可能大

卷轴使不使用、使用多少随意，但一共只有 2 个魔法卷轴

请返回数组尽可能大的累加和

测试链接 §

对数器验证

答案 §

package main
 
import (
	"fmt"
	"math"
	"math/rand"
)
 
// 动态规划
func maxSum1(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
 
	// prefix[i]: 0~i 范围上（nums[:i+1]）一定要用 1 次卷轴的情况下，0~i 范围上整体最大累加和多少
	prefix := make([]int, n)
	// 只有一个数，用 1 次卷轴变成 0
	prefix[0] = 0
	// sum: 每一步的前缀和
	sum := nums[0]
	// maxPreSum: 之前所有前缀和的最大值
	maxPreSum := max(0, sum) // 0 表示一个数都没有的前缀和
	for i := 1; i < n; i++ {
		prefix[i] = max(
			prefix[i-1]+nums[i], // 之前用了 1 次卷轴，当前数不能被刷成 0
			maxPreSum,           // 现在用卷轴，将从之前最大前缀和位置到当前位置都刷成 0
		)
		sum += nums[i]
		maxPreSum = max(maxPreSum, sum)
	}
 
	// suffix[i]: i~n-1 范围上（nums[i:]）一定要用 1 次卷轴的情况下，i~n-1 范围上整体最大累加和多少
	suffix := make([]int, n)
	// 只有一个数，用 1 次卷轴变成 0
	suffix[n-1] = 0
	// sum: 每一步的后缀和
	sum = nums[n-1]
	// maxPreSum: 之前所有后缀和的最大值
	maxPreSum = max(0, sum)
	for i := n - 2; i >= 0; i-- {
		suffix[i] = max(suffix[i+1]+nums[i], maxPreSum)
		sum += nums[i]
		maxPreSum = max(maxPreSum, sum)
	}
 
	// 情况 1: 完全不使用卷轴
	p1 := sum
	// 情况 2: 必须用 1 次卷轴
	p2 := prefix[n-1]
	// 情况 3: 必须用 2 次卷轴
	p3 := math.MinInt
	for i := 1; i < n; i++ {
		// 枚举所有的划分点 i
		// 0~i-1: 左
		// i~n-1: 右
		// 左边使用一次卷轴，右边使用一次卷轴
		p3 = max(p3, prefix[i-1]+suffix[i])
	}
 
	return max(p1, p2, p3)
}
 
// 暴力方法
func maxSum2(nums []int) int {
	n := len(nums)
	p1 := 0
	for _, num := range nums {
		p1 += num
	}
	p2 := mustOneScroll(nums)
	p3 := math.MinInt
	for i := 1; i < n; i++ {
		p3 = max(p3, mustOneScroll(nums[:i])+mustOneScroll(nums[i:]))
	}
	return max(p1, p2, p3)
}
 
// 暴力方法
// 一定要用一次卷轴情况下的最大累加和
func mustOneScroll(nums []int) int {
	ans := math.MinInt
	n := len(nums)
	// i~j 范围使用卷轴刷成 0
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			curAns := 0
			for k := 0; k < i; k++ {
				curAns += nums[k]
			}
			for k := j + 1; k < n; k++ {
				curAns += nums[k]
			}
			ans = max(ans, curAns)
		}
	}
	return ans
}
 
const (
	N          = 50
	V          = 100
	TEST_TIMES = 10000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		arr := randomArray()
		ans1 := maxSum1(arr)
		ans2 := maxSum2(arr)
		if ans1 != ans2 {
			panic("error")
		}
	}
	fmt.Println("ok")
}
 
func randomArray() []int {
	n := rand.Intn(N)
	arr := make([]int, n)
	for i := range arr {
		arr[i] = rand.Intn(V<<1+1) - V
	}
	return arr
}

复杂度 §

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题目4.三个无重叠子数组的最大和 §

题目描述 §

给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组，并返回这三个子数组。

以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。

示例 1：

输入：nums = [1,2,1,2,6,7,5,1], k = 2

输出：[0,3,5]

解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。

示例 2：

输入：nums = [1,2,1,2,1,2,1,2,1], k = 2

输出：[0,2,4]

提示：

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] < 216
• 1 <= k <= floor(nums.length / 3)

测试链接 §

689.三个无重叠子数组的最大和

思路 §

要构建 3 个前缀信息：

1. sum[i]：以 i 开头，往后数 k 长度的子数组（即：nums[i:i+k]）的累加和
2. prefix[i]：0~i 范围上（即：nums[0:i+1]），所有长度为 k 的子数组中累加和最大的子数组的开头位置
3. suffix[i]：i~n-1 范围上（即：nums[i:n-1]），所有长度为 k 的子数组中累加和最大的子数组的开头位置

正式流程：遍历 nums，0~i-1 选一个最大累加和的子数组（即 prefix[i-1]），i~i+k 是第二个子数组，i+k+1~n-1 选一个最大累加和的子数组（即 suffix[i+k+1]）

答案 §

func maxSumOfThreeSubarrays(nums []int, k int) []int {
	n := len(nums)
	// 以 i 开头，往后数 k 长度的子数组（即：nums[i:i+k]）的累加和
	sums := make([]int, n)
	sum := 0
	for l, r := 0, 0; r < n; r++ {
		sum += nums[r]
		if r-l+1 == k {
			sums[l] = sum
			sum -= nums[l]
			l++
		}
	}
	// 0~i 范围上（即：nums[0:i+1]），所有长度为 k 的子数组中累加和最大的子数组的开头位置
	prefix := make([]int, n)
	for l, r := 1, k; r < n; l, r = l+1, r+1 {
		// 这里不取 >=，因为要最小的字典序
		if sums[l] > sums[prefix[r-1]] {
			// nums[l:l+k] 比 prefix[r-1] 结果更好
			prefix[r] = l
		} else {
			// nums[l:l+k] 不比 prefix[r-1] 结果好
			prefix[r] = prefix[r-1]
		}
	}
	// i~n-1 范围上（即：nums[i:n-1]），所有长度为 k 的子数组中累加和最大的子数组的开头位置
	suffix := make([]int, n)
	suffix[n-k] = n - k
	for l := n - k - 1; l >= 0; l-- {
		// 这里取 >=，因为要最小的字典序
		if sums[l] >= sums[suffix[l+1]] {
			suffix[l] = l
		} else {
			suffix[l] = suffix[l+1]
		}
	}
	a, b, c := 0, 0, 0
	maxx := 0
	for i, j := k, k+k-1; j < n-k; i, j = i+1, j+1 {
		// 0~i-1          i~j       j+1~n-1
		// 最好开头 p      i 开头     最好开头 s
		p := prefix[i-1]
		s := suffix[j+1]
		sum = sums[p] + sums[i] + sums[s]
		// 这里不取 >=，因为要最小的字典序
		if sum > maxx {
			maxx = sum
			a = p
			b = i
			c = s
		}
	}
	return []int{a, b, c}
}

复杂度 §

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题目5.可以翻转 1 次的情况下子数组最大累加和 §

题目描述 §

给定一个数组 nums，现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整

比如翻转 [1,2,3,4,5,6] 的 [2~4] 范围，得到的是 [1,2,5,4,3,6]

返回必须随意翻转 1 次之后，子数组的最大累加和

测试链接 §

对数器验证

思路 §

分析：必须随意翻转 1 次，等同于可以反转 1 次也可以不反转，因为可以反转一个数就是不反转

1. 不反转、在答案子数组内反转、答案子数组完全在反转范围内：都相当于是不反转，就是最基础的 最大子数组和 问题
2. 答案子数组的一部分是经过反转后的：不妨设前一部分反转，没反转部分（以 i 开头的子数组中，最大累加和）+ 反转部分（0~i-1 范围上，以某个位置结尾的子数组中，最大累加和）

答案 §

package main
 
import (
	"fmt"
	"math"
	"math/rand"
)
 
// 动态规划
func maxSumReverse1(nums []int) int {
	n := len(nums)
	// start[i]: 以 i 开头的子数组中，最大累加和
	start := make([]int, n)
	start[n-1] = nums[n-1]
	for i := n - 2; i >= 0; i-- {
		start[i] = max(nums[i], nums[i]+start[i+1])
	}
	ans := start[0]
	// end[i]: 子数组必须以 i-1 结尾，其中的最大累加和
	end := nums[0]
	maxEnd := end
	for i := 1; i < n; i++ {
		ans = max(ans, maxEnd+start[i])
		end = max(nums[i], nums[i]+end)
		maxEnd = max(maxEnd, end)
	}
	// maxEnd: 不反转
	ans = max(ans, maxEnd)
	return ans
}
 
// 暴力方法
func maxSumReverse2(nums []int) int {
	n := len(nums)
	ans := math.MinInt
	for l := 0; l < n; l++ {
		for r := l; r < n; r++ {
			reverse(nums, l, r)
			ans = max(ans, maxSum(nums))
			reverse(nums, l, r)
		}
	}
	return ans
}
 
// nums[l:r+1] 进行逆序调整
func reverse(arr []int, l, r int) {
	for l < r {
		arr[l], arr[r] = arr[r], arr[l]
		l++
		r--
	}
}
 
func maxSum(nums []int) int {
	n := len(nums)
	ans := nums[0]
	pre := nums[0]
	for i := 1; i < n; i++ {
		pre = max(nums[i], nums[i]+pre)
		ans = max(ans, pre)
	}
	return ans
}
 
const (
	N          = 50
	V          = 200
	TEST_TIMES = 20000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		arr := randomArray()
		ans1 := maxSumReverse1(arr)
		ans2 := maxSumReverse2(arr)
		if ans1 != ans2 {
			panic("error")
		}
	}
	fmt.Println("ok")
}
 
func randomArray() []int {
	arr := make([]int, rand.Intn(N)+1)
	for i := range arr {
		arr[i] = rand.Intn(V<<1+1) - V
	}
	return arr
}

题目6.删掉 1 个数字后长度为 k 的子数组最大累加和 §

题目描述 §

给定一个数组 nums，求必须删除一个数字后的新数组中，长度为 k 的子数组最大累加和

删除哪个数字随意

测试链接 §

对数器验证

思路 §

题目转化为：求子数组长度为 k+1 的最大累加和，减去这个子数组的最小值

• 求累加和：滑动窗口
• 求滑动窗口内最小值：单调队列

答案 §

package main
 
import (
	"fmt"
	"math"
	"math/rand"
)
 
// 单调队列
func maxSum1(nums []int, k int) int {
	n := len(nums)
	if n <= k {
		return 0
	}
	// 单调队列：维持窗口内最小值
	window := make([]int, n)
	l, r := 0, 0
	// 窗口累加和
	sum := 0
	ans := math.MinInt
	for i := 0; i < n; i++ {
		// 单调队列：i 位置进入单调队列
		for l < r && nums[window[r-1]] >= nums[i] {
			r--
		}
		window[r] = i
		r++
		sum += nums[i]
		if i >= k {
			ans = max(ans, sum-nums[window[l]])
			if window[l] == i-k {
				// 单调队列：如果单调队列最左侧的位置过期了，从队列中弹出
				l++
			}
			sum -= nums[i-k]
		}
	}
	return ans
}
 
// 暴力方法
func maxSum2(nums []int, k int) int {
	n := len(nums)
	if n <= k {
		return 0
	}
	ans := math.MinInt
	for i := 0; i < n; i++ {
		ans = max(ans, lenKMaxSumWithDel(nums, k, i))
	}
	return ans
}
 
func lenKMaxSumWithDel(nums []int, k int, delIdx int) int {
	n := len(nums)
	ans := math.MinInt
	for i := 0; i <= n-k; i++ {
		if i == delIdx {
			continue
		}
		cur := 0
		for j, cnt := i, 0; cnt < k; j++ {
			if j == delIdx {
				continue
			}
			if j == n {
				cur = math.MinInt
				break
			}
			cur += nums[j]
			cnt++
		}
		ans = max(ans, cur)
	}
	return ans
}
 
const (
	N          = 200
	V          = 1000
	TEST_TIMES = 10000
)
 
func main() {
	for i := 0; i < TEST_TIMES; i++ {
		arr := randomArray()
		k := rand.Intn(N) + 1
		ans1 := maxSum1(arr, k)
		ans2 := maxSum2(arr, k)
		if ans1 != ans2 {
			panic("error")
		}
	}
	fmt.Println("ok")
}
 
func randomArray() []int {
	arr := make([]int, rand.Intn(N)+1)
	for i := range arr {
		arr[i] = rand.Intn(V<<1+1) - V
	}
	return arr
}

复杂度 §

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$