核心思想
子数组最大累加和问题是一个非常经典的问题，也比较简单
但是扩展出的问题很多，在笔试、面试中特别常见
详细的东西看例题来理解
例题
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 <= 105-104 <= nums[i] <= 104
注意：这里面有一个附加问题： 子数组中找到拥有最大累加和的子数组，并返回如下三个信息:
最大累加和子数组的开头 left
最大累加和子数组的结尾 right
最大累加和子数组的累加和 sum 如果不止一个子数组拥有最大累加和，那么找到哪一个都可以
关于这里的 dp，我们之前也是遇到过子数组问题，他们的定义都很像，定义 dp[i]为以 i 位置结尾的子数组的最大累加和。
解法步骤
其实就是讨论当以 i 位置为结尾的子数组，在求解最大累加和时，到底需不需要前面 i-1 位置为结尾的子数组的最大累加和。
直接 max (当前位置，当前位置+前一个位置为结尾的子数组的最大累加和)
找到每个位置为结尾的子数组的最大累加和后，选出其中最大的那个即可
代码如下
package main.java.class070;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_MaximumSubarray
* @description: 子数组最大累加和
* // 给你一个整数数组 nums
* // 返回非空子数组的最大累加和
* // 测试链接 : https://leetcode.cn/problems/maximum-subarray/
* @author: zs宝
* @create: 2025-08-19 10:09
* @Version 1.0
**/public class Code01_MaximumSubarray {
class Solution {
public int maxSubArray(int[] nums) {
return maxSubArray2(nums);
}
/**
严格按照位置的动态规划
*/
public int maxSubArray1(int[] nums) {
int n=nums.length;
//定义dp[i]为以i结尾的最大子数组和
int[]dp=new int[n];
dp[0]=nums[0];
int ans=dp[0];
for(int i=1;i<n;i++){
dp[i]=Math.max(nums[i],nums[i]+dp[i-1]);
ans=Math.max(ans,dp[i]);
}
return ans;
}
/**
严格按照位置的动态规划+空间压缩
*/
public int maxSubArray2(int[] nums) {
int n=nums.length;
//定义dp[i]为以i结尾的最大子数组和
//int[]dp=new int[n];
int pre=nums[0];
int ans=pre;
for(int i=1;i<n;i++){
pre=Math.max(nums[i],nums[i]+pre);
ans=Math.max(ans,pre);
}
return ans;
}
// 如下代码为附加问题的实现
// 子数组中找到拥有最大累加和的子数组
// 并返回如下三个信息:
// 1) 最大累加和子数组的开头left
// 2) 最大累加和子数组的结尾right
// 3) 最大累加和子数组的累加和sum
// 如果不止一个子数组拥有最大累加和，那么找到哪一个都可以
public static int left;
public static int right;
public static int sum;
// 找到拥有最大累加和的子数组
// 更新好全局变量left、right、sum
// 上游调用函数可以直接使用这三个变量
// 相当于返回了三个值
public static void extra(int[] nums) {
int n=nums.length;
sum=Integer.MIN_VALUE;
//定义dp[i]为以i结尾的最大子数组和
//int[]dp=new int[n];
int pre=nums[0];
sum=pre;
//定义变量记录以每个位置为结尾的子数组的左右边界
for(int l=0,r=1;r<n;r++){
if(pre>=0){
pre=pre+nums[r];
}else {
pre=nums[r];
l=r;
}
if(pre>sum){
left=l;
right=r;
sum=pre;
}
}
}
}
}2、打家劫舍
题目描述： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
这其实就是一个不能相邻元素的最大累加和问题 定义 dp[i]为前 i 个数的最大累加和 解法如下：
分类讨论，当前第 i 个数要或者不要
即对应着Math.Max (dp[i-2]+nums[i], dp[i-1])
代码如下
package main.java.class070;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_HouseRobber
* @description: 数组中不能选相邻元素的最大累加和
* // 给定一个数组，可以随意选择数字
* // 但是不能选择相邻的数字，返回能得到的最大累加和
* // 测试链接 : https://leetcode.cn/problems/house-robber/
* @author: zs宝
* @create: 2025-08-19 10:44
* @Version 1.0
**/public class Code02_HouseRobber {
class Solution {
public int rob(int[] nums) {
return rob2(nums);
}
/**
严格按照位置依赖的动态规划
*/
public int rob1(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0],nums[1]);
}
//dp[i]为前i家可以偷到的最高金额
int[]dp=new int[n];
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<n;i++){
//分类讨论，偷不偷当前这家
dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
}
/**
严格按照位置依赖的动态规划+空间压缩
*/
public int rob2(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0],nums[1]);
}
int prepre=nums[0];
int pre=Math.max(nums[0],nums[1]);
for(int i=2,temp;i<n;i++){
//分类讨论，偷不偷当前这家
temp=pre;
pre=Math.max(prepre+nums[i],pre);
prepre=temp;
}
return pre;
}
}
}3、环形子数组的最大和
题目描述： 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
输入：nums = [1,-2,3,-2] 输出：3 解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5] 输出：10 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：nums = [3,-2,2,-3] 输出：3 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
这里，最开始想的是将这个题转化为第一个题那种非环形子数组的最大累加和问题，通过再构造一个长度为 2* n 的数组，里面存放了给定的数组，double_nums[i]=nums[i%n]，但是这样按照第一个题的思路就会出现问题，我们的环形数组的子数组有可能出现从末尾到前面的子数组，但是我们构造的数组用第一种方法会出现很多环形数组找子数组不允许出现的情况，如从 i->i+n 的子数组，这个子数组绝对不肯能在环形子数组中出现。因此这种解法不可用
这个题其实还是要从第一个题演化一下：由于这是个环形数组，那么意思是它可以从后面往前找一个子数组，所以这个题的子数组最大累加和将在下面两个情况出现
没有环特性的子数组，就是一个长为 n 的数组找子数组的最大累加和（即子数组没有从后往前）
有环特性的子数组，即最大累加和的子数组是从后往前的
这个情况下其实就相当于，我们数组两边往中间靠的值选择为子数组，那么这个子数组的累加和是最大的，也就意味着中间那一快没有被选进去的子数组累加和是最小的，由于数组整体的累加和=最大和+最和，那么最大和=整体累加和-最小和。
求最小累加和过程其实与最大一样，只是选择的从最大转为最小
代码如下
package main.java.class070;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_MaximumSumCircularSubarray
* @description: 环形数组的子数组最大累加和
* // 给定一个数组nums，长度为n
* // nums是一个环形数组，下标0和下标n-1是连在一起的
* // 返回环形数组中，子数组最大累加和
* // 测试链接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/
* @author: zs宝
* @create: 2025-08-19 11:02
* @Version 1.0
**/public class Code03_MaximumSumCircularSubarray {
class Solution {
/**
严格按照位置依赖的动态规划+空间压缩
*/
public int maxSubarraySumCircular(int[] nums) {
int n=nums.length;
int maxsum=nums[0],minsum=nums[0],sum=nums[0];
for(int i=1,maxpre=nums[0],minpre=nums[0];i<n;i++){
sum+=nums[i];
maxpre=Math.max(nums[i],nums[i]+maxpre);
maxsum=Math.max(maxpre,maxsum);
minpre=Math.min(nums[i],nums[i]+minpre);
minsum=Math.min(minpre,minsum);
}
return sum==minsum?maxsum:Math.max(maxsum,sum-minsum);
}
}
}4、打家劫舍Ⅱ
题目描述： 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3] 输出：3
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
解题分析： 这个题将数组中不相邻的最大累加和以及环形数组结合了起来，首先考虑到环形的特征以及要求不相邻，那么数组在考虑时如果选了第一个数，就不能选最后一个数，不选第一个数就可以选最后一个数（这是与数组中不相邻的最大累加和最大的不同），因此这道题就可以分类进行讨论，ans=Math. Max (选第一个数，不选第一个数)。 其中无论是选第一个数还是不选第一个数的计算结果都是按照题目 2 的方式--求解数组中不相邻的最大累加和，只是数组的范围不一样
选了第一个数：nums[0]+在 2-n-2 的范围内的数组中不相邻的最大累加和
不选第一个数：在 1-n-1 的范围内的数组中不相邻的最大累加和
此外在第一次写本题时，返利一个错误，上面的选第一个数和不选第一个数的过程都是求解数组中不相邻的最大累加和的过程，但是我最开始的时候在还没有分类讨论时就开始了求解数组中不相邻的最大累加和的过程中的边界判定，以至于后面出错 错误代码如下
class Solution {
public int rob(int[] nums) {
return rob1(nums);
}
public int rob1(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
if(n==2){
return Math.max(nums[0],nums[1]);
}
if(n==3){
return Math.max(Math.max(nums[0],nums[1]),nums[2]);
}
//接下来分两种情况讨论：偷了第一家和不偷第一家
//1、偷第一个(要数组第一个数)
int prepre1=nums[2];
int pre1=n>4?Math.max(nums[2],nums[3]):prepre1;
for(int i=4,temp;i<n-1;i++){
temp=pre1;
pre1=Math.max(pre1,nums[i]+prepre1);
prepre1=temp;
}
pre1+=nums[0];
//2、不偷第一家
int ans2=0;
int prepre2=nums[1];
int pre2=Math.max(nums[1],nums[2]);
for(int i=3,temp;i<n;i++){
temp=pre2;
pre2=Math.max(pre2,nums[i]+prepre2);
prepre2=pre2;
}
return Math.max(pre1,pre2);
}
}正确代码如下
package main.java.class070;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_HouseRobberII
* @description: 环形数组中不能选相邻元素的最大累加和
* // 给定一个数组nums，长度为n
* // nums是一个环形数组，下标0和下标n-1是连在一起的
* // 可以随意选择数字，但是不能选择相邻的数字
* // 返回能得到的最大累加和
* // 测试链接 : https://leetcode.cn/problems/house-robber-ii/
* @author: zs宝
* @create: 2025-08-20 08:52
* @Version 1.0
**/public class Code04_HouseRobberII {
class Solution {
public int rob(int[] nums) {
int n=nums.length;
if(n==1){
return nums[0];
}
//要第一个数的情况和不要第一个数的情况取较大值
return Math.max(best(nums,1,n-1),best(nums,2,n-2)+nums[0]);
}
/**
这里就是纯在一个数组范围内，数组中不能选相邻元素的最大累加和
*/
public int best(int[] nums,int l,int r){
if(l>r){
return 0;
}
if(l==r){
return nums[l];
}
if(l+1==r){
return Math.max(nums[l],nums[l+1]);
}
int prepre=nums[l];
int pre=Math.max(nums[l],nums[l+1]);
for(int i=l+2,cur;i<=r;i++){
cur=Math.max(pre,nums[i]+prepre);
prepre=pre;
pre=cur;
}
return pre;
}
}
}5、打家劫舍Ⅳ
题目描述： 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
示例 1：
输入：nums = [2,3,5,9], k = 2 输出：5 解释： 小偷窃取至少 2 间房屋，共有 3 种方式：
窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。 因此，返回 min(5, 9, 9) = 5 。
示例 2：
输入：nums = [2,7,9,3,1], k = 2 输出：2 解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。
代码如下
package main.java.class070;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_HouseRobberIV
* @description: 打家劫舍 IV
* // 沿街有一排连续的房屋。每间房屋内都藏有一定的现金
* // 现在有一位小偷计划从这些房屋中窃取现金
* // 由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
* // 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
* // 给你一个整数数组 nums 表示每间房屋存放的现金金额
* // 第i间房屋中放有nums[i]的钱数
* // 另给你一个整数k，表示小偷需要窃取至少 k 间房屋
* // 返回小偷需要的最小窃取能力值
* // 测试链接 : https://leetcode.cn/problems/house-robber-iv/
* @author: zs宝
* @create: 2025-08-20 09:53
* @Version 1.0
**/public class Code05_HouseRobberIV {
class Solution {
public int minCapability(int[] nums, int k) {
int n=nums.length;
int l=nums[0];
int r=nums[0];
//寻找最大/小值
for(int i=1;i<n;i++){
l=Math.min(l,nums[i]);
r=Math.max(r,nums[i]);
}
//二分答案法
int m=0,ans=0;
while(l<=r){
m=((r-l)>>1)+l;
if(f3(nums,n,m)>=k){
r=m-1;
ans=m;
}else{
l=m+1;
}
}
return ans;
}
/**
严格按照位置依赖的动态规划（其实就是数组不相邻的数的最大累加和，只不过要受到ability的限制，并且求的不再是最大金额数，而是房屋数量）
盗贼的窃取能力为 ability
返回最多可以窃取的房屋数量
*/
public int f1(int[]nums,int n,int ability){
if(n==1){
return nums[0]<=ability?1:0;
}
if(n==2){
return Math.min(nums[0],nums[1])<=ability?1:0;
}
int []dp=new int[n];
dp[0]=nums[0]<=ability?1:0;
dp[1]=Math.min(nums[0],nums[1])<=ability?1:0;
for(int i=2;i<n;i++){
dp[i]=Math.max(dp[i-1],(nums[i]<=ability?1:0)+dp[i-2]);
}
return dp[n-1];
}
/**
严格按照位置依赖的动态规划+空间压缩
盗贼的窃取能力为 ability
返回最多可以窃取的房屋数量
*/
public int f2(int[]nums,int n,int ability){
if(n==1){
return nums[0]<=ability?1:0;
}
if(n==2){
return (nums[0]<=ability || nums[1]<=ability)?1:0;
}
int prepre=nums[0]<=ability?1:0;
int pre=(nums[0]<=ability || nums[1]<=ability)?1:0;
for(int i=2,cur;i<n;i++){
cur=Math.max(pre,prepre+(nums[i]<=ability?1:0));
prepre=pre;
pre=cur;
}
return pre;
}
/**
盗贼的窃取能力为 ability
返回最多可以窃取的房屋数量
反正只计算的是房屋数量，那么直接看房屋可偷就行 */
public int f3(int[]nums,int n,int ability){
int ans=0;
for(int i=0;i<n;i++){
if(ability>=nums[i]){
ans++;
i++;
}
}
return ans;
}
}
}6、最大子矩阵
题目描述： 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
注意：本题相对书上原题稍作改动
示例：
输入： [ [-1,**0**], [0,-1] ] 输出：[0,1,0,1] 解释：输入中标粗的元素即为输出所表示的矩阵
说明：
1 <= matrix.length, matrix[0].length <= 200
这个题最开始写的时候思路没有出错，但是在实现的过程中出现以下问题
在 pre/cur > max/sum 后只更新了 left，right，忘记更新 max/sum 的值
Max 值初始化为 0，但是这个矩阵有负数，这就会造成后续求解过程中，比较 pre/cur 和对应max，sum, 比较的所有情况不全面而造成错误。
代码如下
package main.java.class070;
import java.util.Arrays;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_MaximumSubmatrix
* @description: 子矩阵最大累加和问题
* // 给定一个二维数组grid，找到其中子矩阵的最大累加和
* // 返回拥有最大累加和的子矩阵左上角和右下角坐标
* // 如果有多个子矩阵都有最大累加和，返回哪一个都可以
* // 测试链接 : https://leetcode.cn/problems/max-submatrix-lcci/
* @author: zs宝
* @create: 2025-08-20 10:32
* @Version 1.0
**/public class Code06_MaximumSubmatrix {
/**
* 严格按照位置依赖的动态规划+空间压缩
* @param matrix
* @return
*/
public static int[] getMaxMatrix1(int[][] matrix) {
int n=matrix.length;
int m=matrix[0].length;
int sum=Integer.MIN_VALUE;
int[]ans=new int[4];
int[]nums=new int[m];
for(int i=0;i<n;i++){
Arrays.fill(nums,0);
for(int j=i,cur=0;j<n;j++){
for(int k=0;k<m;k++){
nums[k]+=matrix[j][k];
}
//计算这之间的最大子矩阵
cur=f1(nums,m);
if(cur>sum){
sum=cur;
ans[0]=i;
ans[1]=left;
ans[2]=j;
ans[3]=right;
}
}
}
return ans;
}
public static int left,right;
/**
求解连续子数组的最大累加和
*/
public static int f1(int[]nums,int m){
left=0;
right=0;
int pre=0;
int l=0;
int sum_max=Integer.MIN_VALUE;
for(int r=0;r<m;r++){
if(pre>0){
pre=pre+nums[r];
}else{
pre=nums[r];
l=r;
}
if(pre>sum_max){
sum_max=pre;
left=l;
right=r;
}
}
return sum_max;
}
/**
* 严格按照位置依赖的动态规划+空间压缩+进一步压缩
* @param grid
* @return
*/
public static int[] getMaxMatrix2(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int max = Integer.MIN_VALUE;
int a = 0, b = 0, c = 0, d = 0;
int[] nums = new int[m];
for (int up = 0; up < n; up++) {
Arrays.fill(nums, 0);
for (int down = up; down < n; down++) {
// 如下代码就是题目1的附加问题 : // 子数组中找到拥有最大累加和的子数组
for (int l = 0, r = 0, pre = Integer.MIN_VALUE; r < m; r++) {
nums[r]+=grid[down][r];
if(pre>0){
pre+=nums[r];
}else{
pre=nums[r];
l=r;
}
if(pre>max){
max=pre;
a=up;
b=l;
c=down;
d=r;
}
}
}
}
return new int[] { a, b, c, d };
}
}