052.子数组最大累加和问题与扩展-上

前置知识：二分答案法（题目 5 需要这个重要技巧）、从递归入手一维动态规划（本节都是一维动态规划的问题）

子数组最大累加和问题是一个非常经典的问题，也比较简单

但是扩展出的问题很多，在笔试、面试中特别常见

扩展出的问题很多非常有趣，解法也比较巧妙，用本节和 下节 两期来给讲述

题目1.最大子数组和 §

题目描述 §

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

示例 2：

输入：nums = [1]

输出：1

示例 3：

输入：nums = [5,4,-1,7,8]

输出：23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

测试链接 §

53.最大子数组和

答案 §

最大子数组和

动态规划 §

func maxSubArray(nums []int) int {
	n := len(nums)
	// dp[i]: 以 i 结尾的最大子数组和
	dp := make([]int, n)
	// 初始化：数组只有一个数
	dp[0] = nums[0]
	ans := dp[0]
	for i := 1; i < n; i++ {
		dp[i] = max(
			nums[i],         // 只要当前值，舍弃前面的
			dp[i-1]+nums[i], // 要当前值 + 前面的
		)
		ans = max(ans, dp[i])
	}
	return ans
}

空间压缩 §

func maxSubArray(nums []int) int {
	n := len(nums)
	ans := nums[0]
	pre := nums[0]
	for i := 1; i < n; i++ {
		pre = max(nums[i], pre+nums[i])
		ans = max(ans, pre)
	}
	return ans
}

扩展 §

子数组中找到拥有最大累加和的子数组，并返回如下三个信息：

1. 最大累加和子数组的开头 left
2. 最大累加和子数组的结尾 right
3. 最大累加和子数组的累加和 sum

如果不止一个子数组拥有最大累加和，那么找到哪一个都可以

func extra(nums []int) (left, right, sum int) {
	n := len(nums)
	sum = math.MinInt
	pre := sum
	for l, r := 0, 0; r < n; r++ {
		if pre >= 0 {
			// 吸收前面的累加和有利可图
			// 那就不换开头
			pre += nums[r]
		} else {
			// 吸收前面的累加和已经无利可图
			// 那就换开头
			pre = nums[r]
			l = r
		}
		if pre > sum {
			sum = pre
			left = l
			right = r
		}
	}
	return
}

题目2.数组中不能选相邻元素的最大累加和 §

题目描述 §

给定一个数组，可以随意选择数字（子序列）

但是不能选择相邻的数字，返回能得到的最大累加和

至少要选一个元素

即：经典版的打家劫舍

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400（我们的解法是通用的，元素可以为负）

测试链接 §

198.打家劫舍

答案 §

打家劫舍

题目3.环形子数组的最大和 §

题目描述 §

给定一个数组 nums，长度为 n

nums 是一个环形数组，下标 0 和下标 n-1 是连在一起的

返回环形数组中，子数组最大累加和

至少要选一个元素

提示：

• n == nums.length
• 1 <= n <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4 ​​​​​​​

测试链接 §

918.环形子数组的最大和

思路 §

答案有两种可能：

1. 答案不被隔断：即不考虑环，同 题目1
2. 答案被隔断：即考虑环，子数组的最大和横跨开头和结尾，中间扣掉一个子数组，ans = 数组累加和 - 不考虑环的子数组最小和

两种情况中取较大值就是答案

答案 §

func maxSubarraySumCircular(nums []int) int {
	n := len(nums)
	all := nums[0]
	minSum := nums[0]
	maxSum := nums[0]
	minPre := nums[0]
	maxPre := nums[0]
	for i := 1; i < n; i++ {
		all += nums[i]
		minPre = min(nums[i], minPre+nums[i])
		minSum = min(minSum, minPre)
		maxPre = max(nums[i], maxPre+nums[i])
		maxSum = max(maxSum, maxPre)
	}
	// 至少要选一个元素
	if all == minSum {
		return maxSum
	}
	return max(maxSum, all-minSum)
}

题目4.环形数组中不能选相邻元素的最大累加和 §

题目描述 §

给定一个数组 nums，长度为 n

nums 是一个环形数组，下标 0 和下标 n-1 是连在一起的

可以随意选择数字，但是不能选择相邻的数字

返回能得到的最大累加和

即：环形数组版的打家劫舍

测试链接 §

213.打家劫舍 II

思路 §

答案有两种可能：

1. 不选 nums[0]：变成了 nums[1:n]（不考虑环），同 题目2
2. 不选 nums[n-1]：变成了 nums[0:n-1]（不考虑环）

两种情况中取较大值就是答案

答案 §

打家劫舍 II

题目5.打家劫舍 IV §

题目描述 §

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= (nums.length + 1)/2

测试链接 §

2560.打家劫舍 IV

思路 §

二分答案法

动态规划 §

var (
	theNums []int
	n       int
)
 
func minCapability(nums []int, k int) int {
	theNums = nums
	n = len(nums)
	minn, maxx := nums[0], nums[0]
	for i := 1; i < n; i++ {
		minn = min(minn, nums[i])
		maxx = max(maxx, nums[i])
	}
	// 窃取能力的范围就是 [minn, maxx]
	ans := 0
	for minn <= maxx {
		mid := minn + (maxx-minn)>>1
		if mostRob(mid) >= k {
			ans = mid
			maxx = mid - 1
		} else {
			minn = mid + 1
		}
	}
	return ans
}
 
// 盗贼能力为 ability 时，盗贼最多能窃取多少间房屋
// 限制：不能窃取相邻房屋、能力足够才能偷
func mostRob(ability int) int {
	dp0 := 0
	if ability >= theNums[0] {
		dp0 = 1
	}
	if n == 1 {
		return dp0
	}
	dp1 := 0
	if ability >= theNums[0] || ability >= theNums[1] {
		dp1 = 1
	}
	for i := 2; i < n; i++ {
		can := 0
		if ability >= theNums[i] {
			can = 1
		}
		dp0, dp1 = dp1, max(dp0+can, dp1)
	}
	return dp1
}

贪心 §

因为求的是最大能偷几间房，而不是最大偷窃金额，所以可以贪心：能偷就偷，尽早偷

var (
	theNums []int
	n       int
)
 
func minCapability(nums []int, k int) int {
	theNums = nums
	n = len(nums)
	minn, maxx := nums[0], nums[0]
	for i := 1; i < n; i++ {
		minn = min(minn, nums[i])
		maxx = max(maxx, nums[i])
	}
	// 窃取能力的范围就是 [minn, maxx]
	ans := 0
	for minn <= maxx {
		mid := minn + (maxx-minn)>>1
		if mostRob(mid) >= k {
			ans = mid
			maxx = mid - 1
		} else {
			minn = mid + 1
		}
	}
	return ans
}
 
// 贪心：能偷就偷，尽早偷
// 盗贼能力为 ability 时，盗贼最多能窃取多少间房屋
// 限制：不能窃取相邻房屋、能力足够才能偷
func mostRob(ability int) int {
	ans := 0
	for i := 0; i < n; i++ {
		if ability >= theNums[i] {
			ans++
			i++ // 这里跳一步、for 跳一步，共两步
		}
	}
	return ans
}

复杂度 §

• 时间复杂度：两种方法都是 $O(n\ast lo{g}_2^{max-min+1})$
  • 二分答案：$O(lo{g}_2^{max-min+1})$
  • 每次二分 mostRob 方法：$O(n)$
  • 贪心常数时间更好
• 空间复杂度：$O(1)$

题目6.子矩阵最大累加和问题 §

题目描述 §

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

说明：

• 1 <= matrix.length, matrix[0].length <= 200

测试链接 §

面试题 17.24.最大子矩阵

思路 §

数组压缩技巧：求以每一行为底的结果

同 题目1扩展

答案 §

func getMaxMatrix(matrix [][]int) []int {
	n := len(matrix)
	m := len(matrix[0])
	r1, c1, r2, c2 := 0, 0, 0, 0
	// 数组压缩技巧：求以每一行为底的结果
	nums := make([]int, m)
	maxx := math.MinInt
	for up := 0; up < n; up++ {
		// up 改变，nums 进行初始化
		for i := range nums {
			nums[i] = 0
		}
		for down := up; down < n; down++ {
			// nums 每个元素累加 up~down 的数据
			// 题目转换为：一维数组中找到拥有最大累加和的子数组
			for l, r, pre := 0, 0, math.MinInt; r < m; r++ {
				nums[r] += matrix[down][r]
				if pre >= 0 {
					pre += nums[r]
				} else {
					pre = nums[r]
					l = r
				}
				if pre > maxx {
					maxx = pre
					r1 = up
					c1 = l
					r2 = down
					c2 = r
				}
			}
		}
	}
	return []int{r1, c1, r2, c2}
}

复杂度 §

• 时间复杂度：$O(n^2\ast m)$，已是最优解
  • 遍历 up 和 down：$O(n^2)$
  • 一维数组中找到拥有最大累加和的子数组：$O(m)$
• 空间复杂度：$O(m)$