核心思想
本节课是上节课内容的继续，见识更多与累加和相关的题目 而且有 4 个题来自真实大厂笔试题，都提供了对数器的验证代码来确保正确 很多解法的思路非常巧妙
例题
1、乘积最大子数组
题目描述： 给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10nums的任何子数组的乘积都 保证 是一个 32-位 整数
代码如下：题解分析在代码的注释中
package main.java.class071;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_MaximumProductSubarray
* @description: 乘积最大子数组
* // 给你一个整数数组 nums
* // 请你找出数组中乘积最大的非空连续子数组
* // 并返回该子数组所对应的乘积
* // 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/
* @author: zs宝
* @create: 2025-08-21 10:18
* @Version 1.0
**/public class Code01_MaximumProductSubarray {
class Solution {
public int maxProduct(int[] nums) {
int n=nums.length;
//因为这是关于乘积的最大子数组和，不是之前的关于加法的
//关于乘法，是不同于之前的加法的，加法dp[i]只需要关注与dp[i-1]是大于0还是小于0,大于0则nums[i]加上就可以增大，小于0就不管
//但是对于乘法，如果当前nums[i]为负数时，前面如果i-1有乘积最小的值为负数的话，那么两者相乘，绝对会增大，这是最容易忽略的考虑点
//同时如果nums[i]大于0，则需要考虑前i-1是否为最大值相乘大于当前nums[i]值
//所以针对上述的可能情况，我们每次往后更新时，都需要维护一个前面子数组乘积的最大值，最小值
//所以会定义两个dp数组，max[i]:前i个数字中的以i结尾的子数组中累乘的最大值，min[i]:前i个数字中的以i结尾的子数组中累乘的最小值
double ans=nums[0],min=nums[0],max=nums[0],currentMax=nums[0],currentMin=nums[0];
for(int i=1;i<n;i++){
currentMin=Math.min(nums[i],Math.min(nums[i]*min,nums[i]*max));
currentMax=Math.max(nums[i],Math.max(nums[i]*min,nums[i]*max));
max=currentMax;
min=currentMin;
ans=Math.max(max,ans);
}
return (int)ans;
}
}
}2、子序列累加和必须被 7 整除的最大累加和
这是某个大厂的面试题
给定一个非负数组 nums， 可以任意选择数字组成子序列，但是子序列的累加和必须被 7 整除 返回最大累加和 对数器验证
这个题与我们在 069、从递归入手三维动态规划中的某一个题还是很像的，都是要求中带有整除某个数，那个题我们在 dp 的定义中写过，不能直接定义为 dp 什么的能够被 7 整除的最大累加和，这样的定义无法将前面的状态向后传递，而应该从余数的角度出发。 因此在这里我们定义 dp 【i】【j】为 nums 前 i 个数【0,i-1】上面，整除 7 余 j 的最大累加和是多少。
这样的话，我们在考虑的时候，就会有以下情况
要 nums[i-1]这个数
则需要计算出 nums[i]%7 后，前 i-1 个数还需要余数（假设为 need）为什么样的子序列，即 dp【i-1】【need】
这个时候又要分 nums[i]%7 大于 j 和小于 j 的情况
不要 nums[i]这个数，则 dp【i】【j】=dp【i-1】【j】
这里总结一个小技巧：关于子序列的dp总是会考虑最后一个数值要还是不要，哪怕暴力递归也是这样。 代码如下
package main.java.class071;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_MaxSumDividedBy7
* @description: 子序列累加和必须被7整除的最大累加和
* // 给定一个非负数组nums，
* // 可以任意选择数字组成子序列，但是子序列的累加和必须被7整除
* // 返回最大累加和
* // 对数器验证
* @author: zs宝
* @create: 2025-08-21 10:55
* @Version 1.0
**/public class Code02_MaxSumDividedBy7 {
//正式方法
// 时间复杂度O(n)
public static int maxSum2(int[] nums) {
int n=nums.length;
// dp[i][j] : nums[0...i-1]
// nums前i个数形成的子序列一定要做到，子序列累加和%7 == j
// 这样的子序列最大累加和是多少
// 注意 : dp[i][j] == -1代表不存在这样的子序列
int[][]dp=new int[n+1][7];
//初始化第一行的值
dp[0][0]=0;
//当拿前0个数字（就是没有数字），却要求余数有值的时候，这是根本不可能出现的情况,设为-1
for(int j=1;j<7;j++){
dp[0][j]=-1;
}
for(int i=1,x,cur,need;i<=n;i++){
x=nums[i-1];
cur=nums[i-1]%7;
for(int j=0;j<7;j++){
//不要最后一个值的时候
dp[i][j]=dp[i-1][j];
//考虑要最后一个值的时候
need=cur>j?(7+j-cur):(j-cur);
//当需要的数值是存在的
if(dp[i-1][need]!=-1){
dp[i][j]=Math.max(dp[i][j],dp[i-1][need]+x);
}
}
}
return dp[n][0];
}
// 暴力方法
// 为了验证
public static int maxSum1(int[] nums) {
// nums形成的所有子序列的累加和都求出来
// 其中%7==0的那些累加和中，返回最大的
// 就是如下f函数的功能
return f(nums, 0, 0);
}
public static int f(int[] nums, int i, int s) {
if (i == nums.length) {
return s % 7 == 0 ? s : 0;
}
return Math.max(f(nums, i + 1, s), f(nums, i + 1, s + nums[i]));
}
// 为了测试
// 生成随机数组
public static int[] randomArray(int n, int v) {
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = (int) (Math.random() * v);
}
return ans;
}
// 为了测试
// 对数器
public static void main(String[] args) {
int n = 15;
int v = 30;
int testTime = 20000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * n) + 1;
int[] nums = randomArray(len, v);
int ans1 = maxSum1(nums);
int ans2 = maxSum2(nums);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}3、魔法卷轴
这是某个大厂的面试题
给定一个数组 nums，其中可能有正、负、0 每个魔法卷轴可以把 nums 中连续的一段全变成 0 你希望数组整体的累加和尽可能大 卷轴使不使用、使用多少随意，但一共只有 2 个魔法卷轴 请返回数组尽可能大的累加和 对数器验证
题目分析如下：
这道题说的魔法卷轴不使用、使用多少随意，那么就相当于，要分类讨论，使用0次，1次，2次的情况做比对
这里有提到魔法卷轴可以把 nums 中连续的一段全变成 0，那么没再卷轴改变的那一段的和，正好就是前缀和，后后缀和
使用0次：即整个数组的累加和
使用一次：
我们定义一个prefix[i]表示在nums[0,i-1]上必须用一次卷轴的的最大累加和
那么就会涉及到讨论，在nums[i-1]在卷轴使用范围内，nums[i]不在卷轴使用范围内
prefix[i]就相当于其中的卷轴覆盖到i位置与不覆盖到i位置的最大值
使用两次
两次卷轴是否交叠
若有交叠则本质相当于使用了一次卷轴
不交叠则，相当于求解[0, i-1],[i, n-1]的分别使用一次卷轴的最大累加和之和
其中[0, i-1]可以依靠前缀和，那么[i, n-1]就可以依靠后缀和来辅助求解
关键词： “连续区间和” + “删掉一段/清零一段/取补集” 目标： 求最值（最大/最小）。 第一反应： 这个问题可以转写成「前缀和 - 区间和」，因此考虑用前缀和维护；如果还要在前缀和里取极值，就顺便维护
maxPresum / minPresum。
代码如下：
package main.java.class071;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_MagicScrollProbelm
* @description: 魔法卷轴
* 给定一个数组nums，其中可能有正、负、0，
* 每个魔法卷轴可以把nums中连续的一段全变成0，
* 你希望数组整体的累加和尽可能大，
* 卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴，
* 请返回数组尽可能大的累加和，
* 对数器验证
* @author: zs宝
* @create: 2025-08-22 09:20
* @Version 1.0
**/public class Code03_MagicScrollProbelm {
// 正式方法
// 时间复杂度O(n)
public static int maxSum2(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
//1、第一种情况，一次卷轴都不用
int p1=0;
for(int num:nums){
p1+=num;
}
//2、开始讨论第二种情况，必须用一次卷轴
//prefix[i]表示在nums[0,i-1]上必须用一次卷轴的的最大累加和
int[]prefix=new int[n];
//对于这其中的运算会有2种讨论：在nums[i-1]在卷轴使用范围内，nums[i]不在卷轴使用范围内
//数组依次累加和
int sum=nums[0];
//表示[0,i-1]最大的前缀和
int maxPrefix=Math.max(0,nums[0]);
for(int i=1;i<n;i++){
//这里就表示了，在nums[i-1]在卷轴使用范围内，nums[i-1]不在卷轴使用范围内的两种讨论
//maxPrefix：在nums[i-1]在卷轴使用范围内； prefix[i-1]+nums[i]：nums[i-1]不在卷轴使用范围内
//同时因为maxPrefix表示最大前缀和，因此不被包含在这个最大前缀和的数都是使用了卷轴的数
prefix[i]=Math.max(maxPrefix,prefix[i-1]+nums[i]);
sum+=nums[i];
//同时，每一轮的sum都表示在[0,i-1]的累加和，其实也就可以当成一个[0,i-1]的前缀和
maxPrefix=Math.max(maxPrefix,sum);
}
//所以最后在整个数组上只使用一次卷轴的最大累加和就为prefix[n-1]
int p2=prefix[n-1];
//3、接下来讨论第三种情况，在数组上一定使用了2次魔法卷轴的情况
//这里我们要讨论一下情况，即两次使用的卷轴会不会有重叠部分
//假设两次使用的卷轴有重叠部分如[1,4],[3,7]-->那么仔细想想这交叠后的使用范围就是[1,7]就可以当作使用了一次卷轴
//所以针对使用两次卷轴的情况，只需要关系两次使用卷轴没有交叠部分的时候即可，
//即假设有个中间位置i将两次使用卷轴的范围区分开来，
//那么使用两次卷轴的最大累加和就是[0,i-1]上使用一次卷轴和[i,n-1]上使用一次卷轴的最大累加和之和
//那么对于[i,n-1]上使用一次卷轴的最大累加和就相当于prefix[i]的反面-->由后缀和来求
//suffix[i]:在i,n-1上面使用一次卷轴的最大累加和
int[]suffix=new int[n];
//所有后缀的依次叠加
sum=nums[n-1];
//表示[i,n-1]最大的前缀和
int maxSuffix=Math.max(0,nums[n-1]);
for(int i=n-2;i>=0;i--){
suffix[i]=Math.max(maxSuffix,suffix[i+1]+nums[i]);
sum+=nums[i];
maxSuffix=Math.max(sum,maxSuffix);
}
//接下来分别依次讨论，以不同的点作为两次卷轴使用的分界点的情况
int p3=Integer.MIN_VALUE;
for(int i=1;i<n;i++){
p3=Math.max(p3,(prefix[i-1]+suffix[i]));
}
return Math.max(p1,Math.max(p2,p3));
}
// 暴力方法
// 为了测试
public static int maxSum1(int[] nums) {
int p1 = 0;
for (int num : nums) {
p1 += num;
}
int n = nums.length;
int p2 = mustOneScroll(nums, 0, n - 1);
int p3 = Integer.MIN_VALUE;
for (int i = 1; i < n; i++) {
p3 = Math.max(p3, mustOneScroll(nums, 0, i - 1) + mustOneScroll(nums, i, n - 1));
}
return Math.max(p1, Math.max(p2, p3));
}
// 暴力方法
// 为了测试
// nums[l...r]范围上一定要用一次卷轴情况下的最大累加和
public static int mustOneScroll(int[] nums, int l, int r) {
int ans = Integer.MIN_VALUE;
// l...r范围上包含a...b范围
// 如果a...b范围上的数字都变成0
// 返回剩下数字的累加和
// 所以枚举所有可能的a...b范围
// 相当暴力，但是正确
for (int a = l; a <= r; a++) {
for (int b = a; b <= r; b++) {
// l...a...b...r
int curAns = 0;
for (int i = l; i < a; i++) {
curAns += nums[i];
}
for (int i = b + 1; i <= r; i++) {
curAns += nums[i];
}
ans = Math.max(ans, curAns);
}
}
return ans;
}
// 为了测试
public static int[] randomArray(int n, int v) {
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = (int) (Math.random() * (v * 2 + 1)) - v;
}
return ans;
}
// 为了测试
public static void main(String[] args) {
int n = 50;
int v = 100;
int testTime = 10000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * n);
int[] nums = randomArray(len, v);
int ans1 = maxSum1(nums);
int ans2 = maxSum2(nums);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}4、三个无重叠子数组的最大和
给你一个整数数组 nums 和一个整数 k 找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组 并返回这三个子数组 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置 如果有多个结果，返回字典序最小的一个
题目分析：
这个题是想要我阿弥能找出三个长度为k的子数组，求累加和的和最大的那三个
这个题和上面哪一个魔法卷轴题很像，魔法卷轴题是分为2个，我们这个是分为3个
那么我们这个题假设我已经找到了对应的三段子数组，现在确认中间那段的位置，则整个数组，被分成3段，中间那段在第二段
我们在确认中间那段的情况下，只需要找到第一段的长度为k的子数组中累加和最大的那个；以及第三段中长度为k的子数组中累加和最大的那个
由此就有定义prefix[i]为[0, i]上长度为k的子数组累加和的最大值的起点，suffix[i]为[i, n-1]上长度为k的子数组累加和最大值的起点
然后依次举例中间这段的可能性情况，找出对应的三段求和即可
代码如下
package main.java.class071;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_MaximumSum3UnoverlappingSubarrays
* @description: 三个无重叠子数组的最大和,
* 给你一个整数数组 nums 和一个整数 k,
* 找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组,
* 并返回这三个子数组,
* 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置,
* 如果有多个结果，返回字典序最小的一个
* 测试链接 :
* @author: zs宝
* @create: 2025-08-22 10:53
* @Version 1.0
**/public class Code04_MaximumSum3UnoverlappingSubarrays {
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n=nums.length;
int[]sums=new int[n];
//接下来求解以每个位置作为起点，长度为k的累加和
for(int l=0,r=0,sum=0;r<n;r++){
sum+=nums[r];
if(r-l+1==k){
sums[l]=sum;
//不要忘记滑动窗口右移时，最左边的数字弹出
sum-=nums[l];
l++;
}
}
//定义prefix[i]为[0,i]上长度为k的子数组累加和的最大值的起点
//则初始时prefix[k-1]=0;因为就只有这一个长度k子数组
int[]prefix=new int[n];
for(int l=1,r=k;r<n;l++,r++){
//sum[l]表示当前l->r长度为k的子数组，prefix[r-1]表示面的长度为k的子数组的最大累加和
if(sums[l]>sums[prefix[r-1]]){
prefix[r]=l;
}else{
prefix[r]=prefix[r-1];
}
}
//定义suffix[i]为[i,n-1]上长度为k的子数组累加和最大值的起点
//则初始时suffix[n-k]的值为n-k
int[]suffix=new int[n];
suffix[n-k]=n-k;
for(int l=n-k-1;l>=0;l--){
if(sums[l]>=sums[suffix[l+1]]){
// 注意>=，为了同样最大累加和的情况下，最小的字典序
suffix[l]=l;
}else{
suffix[l]=suffix[l+1];
}
}
//接下来将数组分成三份，依次求解三个无重叠数组和的最大值
//我们只遍历中间那份
int a=0,b=0,c=0;
int max=Integer.MIN_VALUE;
for(int l=k,r=2*k-1,sum;r<n-k;r++,l++){
sum=sums[l]+sums[prefix[l-1]]+sums[suffix[r+1]];
if(sum>max){
max=sum;
a=prefix[l-1];
b=l;
c=suffix[r+1];
}
}
return new int[]{a,b,c};
}
}
}5、可以翻转 1 次的情况下子数组最大累加和
这是某个大厂的面试题
给定一个数组 nums， 现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整 比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6] 返回必须随意翻转 1 次之后，子数组的最大累加和 对数器验证
解法核心思路
不翻转的情况 直接是求解最大子数组累加和算法：最大子数组和。作为基准答案。
翻转一次的情况 直觉是：翻转一段
[L..R]，等于把 左边的“最好后缀” 和 右边的“最好前缀” 拼到一起，中间那段被翻转到另一边，不再阻碍。举例：
[5, -100, 6]→ 如果翻转[-100, 6]，就能把6拼到5后面，得到[5,6]。
如何高效求拼接？
先预处理：
start[i]= 以i开始的最大子数组和（从右往左 Kadane）。maxEnd[i]= 以i结尾的最大子数组和（从左往右 Kadane）。
枚举切分点
i：candidate = maxEnd[i] + start[i+1]这表示翻转[i+1..j]这一段，把start[i+1]的那部分“搬”到maxEnd[i]的后面。
最终答案
ans = max( 不翻转的Kadane结果, 所有 candidate )
当我看到「允许一次翻转 / 删除 / 清零」+「最大子数组和」时， 我要想到：
不操作的 Kadane 结果；
一次操作的价值 = 左最大后缀 + 右最大前缀 拼接；
答案是二者最大值。
代码如下
package main.java.class071;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_ReverseArraySubarrayMaxSum
* @description: 可以翻转1次的情况下子数组最大累加和，
* 给定一个数组nums，
* 现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整，
* 比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6]，
* 返回必须随意翻转1次之后，子数组的最大累加和，
* 对数器验证
* @author: zs宝
* @create: 2025-08-23 09:33
* @Version 1.0
**/public class Code05_ReverseArraySubarrayMaxSum {
// 正式方法
// 时间复杂度O(n)
public static int maxSumReverse2(int[] nums) {
int n=nums.length;
//start[i]：以i为开头的最大累加和
int[]start=new int[n];
start[n-1]=nums[n-1];
for(int i=n-2;i>=0;i--){
start[i]=Math.max(nums[i],start[i+1]+nums[i]);
}
//接下来执行求解前半部分，那部分的最大值
//ans表示以i为划分，[0,i-1]部分翻转后与[i,n-1]的结合最大值
//初始化为翻转0位置，即从未翻转过
int ans=start[0];
//必须以i结尾的最大累加和
int end=nums[0];
//必须以i结尾的最大累加和中的最大值
int maxEnd=nums[0];
for(int i=1;i<n;i++){
//依次枚举不同位置作为划分点，寻找翻转最大值
ans=Math.max(ans,maxEnd+start[i]);
end=Math.max(nums[i],end+nums[i]);
maxEnd=Math.max(end,maxEnd);
}
//最后再比较数组从未翻转过时的最大子数组累加和与有翻转的最大累加和。
ans=Math.max(ans,maxEnd);
return ans;
}
// 暴力方法
// 为了验证
public static int maxSumReverse1(int[] nums) {
int ans = Integer.MIN_VALUE;
for (int l = 0; l < nums.length; l++) {
for (int r = l; r < nums.length; r++) {
reverse(nums, l, r);
ans = Math.max(ans, maxSum(nums));
reverse(nums, l, r);
}
}
return ans;
}
// nums[l...r]范围上的数字进行逆序调整
public static void reverse(int[] nums, int l, int r) {
while (l < r) {
int tmp = nums[l];
nums[l++] = nums[r];
nums[r--] = tmp;
}
}
// 返回子数组最大累加和
public static int maxSum(int[] nums) {
int n = nums.length;
int ans = nums[0];
for (int i = 1, pre = nums[0]; i < n; i++) {
pre = Math.max(nums[i], pre + nums[i]);
ans = Math.max(ans, pre);
}
return ans;
}
// 为了测试
// 生成随机数组
public static int[] randomArray(int n, int v) {
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = (int) (Math.random() * (v * 2 + 1)) - v;
}
return ans;
}
// 为了测试
// 对数器
public static void main(String[] args) {
int n = 50;
int v = 200;
int testTime = 20000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * n) + 1;
int[] arr = randomArray(len, v);
int ans1 = maxSumReverse1(arr);
int ans2 = maxSumReverse2(arr);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}6、删掉 1 个数字后长度为 k 的子数组最大累加和
这是某个大厂的面试题
给定一个数组 nums，求必须删除一个数字后的新数组中 长度为 k 的子数组最大累加和，删除哪个数字随意 对数器验证
注意： 这道题会使用到单调队列
解法思路：
将删除一个数字后的新数组中 长度为 k 的子数组最大累加和，转变为长度为k+1的子数组累加和删除其中的最小值后的值，枚举找到所有当中的最大值
package main.java.class071;
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_DeleteOneNumberLengthKMaxSum
* @description: 删掉1个数字后长度为k的子数组最大累加和,
* 给定一个数组nums，求必须删除一个数字后的新数组中,
* 长度为k的子数组最大累加和，删除哪个数字随意,
* 对数器验证
* @author: zs宝
* @create: 2025-08-23 10:34
* @Version 1.0
**/public class Code06_DeleteOneNumberLengthKMaxSum {
// 正式方法
// 时间复杂度O(N)
public static int maxSum2(int[] nums, int k) {
int n=nums.length;
//根本不足以进行删除一个数字的操作
if(n<=k){
return 0;
}
//单调队列 ，队列头维持当前窗口内的最小值
int[]windows=new int[n];
int l=0;
int r=0;
int ans=Integer.MIN_VALUE;
int sum=0;
for(int i=0;i<n;i++){
//单调队列中移除比新进来的数大的数，因为每次长度为k+1的窗口内减去最小的值
while(l<r && nums[i]<=nums[windows[r-1]]){
r--;
}
windows[r++]=i;
sum+=nums[i];
//当i>=k时，即已经累和了至少k+1个元素，可以进行删除操作了
if(i>=k){
ans=Math.max(ans,sum-nums[windows[l]]);
//注意单调队列最左的边界是否还能在长度为k的窗口内
if(i-k==windows[l]){
l++;
}
//后续每次迭代都要减去长度为k+1的滑动窗口的左边界的值
sum-=nums[i-k];
}
}
return ans;
}
// 暴力方法
// 为了测试
public static int maxSum1(int[] nums, int k) {
int n = nums.length;
if (n <= k) {
return 0;
}
int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int[] rest = delete(nums, i);
ans = Math.max(ans, lenKmaxSum(rest, k));
}
return ans;
}
// 暴力方法
// 为了测试
// 删掉index位置的元素，然后返回新数组
public static int[] delete(int[] nums, int index) {
int len = nums.length - 1;
int[] ans = new int[len];
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (j != index) {
ans[i++] = nums[j];
}
}
return ans;
}
// 暴力方法
// 为了测试
// 枚举每一个子数组找到最大累加和
public static int lenKmaxSum(int[] nums, int k) {
int n = nums.length;
int ans = Integer.MIN_VALUE;
for (int i = 0; i <= n - k; i++) {
int cur = 0;
for (int j = i, cnt = 0; cnt < k; j++, cnt++) {
cur += nums[j];
}
ans = Math.max(ans, cur);
}
return ans;
}
// 为了测试
// 生成长度为n，值在[-v, +v]之间的随机数组
public static int[] randomArray(int n, int v) {
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = (int) (Math.random() * (2 * v + 1)) - v;
}
return ans;
}
// 为了测试
// 对数器
public static void main(String[] args) {
int n = 200;
int v = 1000;
int testTimes = 10000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int len = (int) (Math.random() * n) + 1;
int[] nums = randomArray(len, v);
int k = (int) (Math.random() * n) + 1;
int ans1 = maxSum1(nums, k);
int ans2 = maxSum2(nums, k);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}总结
最后再总结一下，子数组最大累加和问题与扩展这部分题目的关系
最大子数组和（母题）
│
├── 1. 经典 Kadane 算法
│ dp[i] = max(nums[i], dp[i-1] + nums[i])
│
├── 2. 打家劫舍系列（不相邻约束）
│ dp[i] = max(dp[i-1], dp[i-2] + nums[i])
│ └─ 打家劫舍 II（环形房子）：
│ max( rob(nums[0..n-2]), rob(nums[1..n-1]) )
│
├── 3. 环形子数组最大和
│ maxSum = max( Kadane(nums),
│ totalSum - Kadane(minSubarray) )
│
├── 4. 最大乘积子数组
│ maxProd[i] = max(nums[i], maxProd[i-1]*nums[i], minProd[i-1]*nums[i])
│ minProd[i] = min(nums[i], maxProd[i-1]*nums[i], minProd[i-1]*nums[i])
│
├── 5. 最大子矩阵和
│ 固定上下边界 → 压缩列和 → 在一维数组上跑 Kadane
│ res = max( res, Kadane(sum[colL..colR]) )
│
├── 6. 允许一次操作
│ ├─ 删除一个元素：
│ left[i] = max subarray ending at i
│ right[i] = max subarray starting at i
│ ans = max(left[i-1] + right[i+1])
│
│ ├─ 翻转一次子数组：
│ ans = max( 前缀最大 + 翻转段 + 后缀最大 )
│
│ └─ 清零一次/两次（魔法卷轴）：
│ dp[i][used] 表示到 i 且已用 used 次卷轴的最大和
│
├── 7. 固定长度子数组最大和
│ 滑动窗口：sum[i..i+k-1]
│ 或 单调队列维护窗口内最大/最小值
│
└── 8. 多个不重叠子数组
├─ 两个子数组：前缀最大 + 后缀最大拼接
└─ 三个子数组（LC 689）：前缀最优、中间段、后缀最优