class071 子数组最大累加和问题与扩展-下【算法】
code1 152. 乘积最大子数组
// 乘积最大子数组
// 给你一个整数数组 nums
// 请你找出数组中乘积最大的非空连续子数组
// 并返回该子数组所对应的乘积
// 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/
因为有负数，并且有负负得正
dp[i]：[0…i]子数组最大成绩
- nums[i]
- nums[i]x最大[i-1]
- nums[i]x最小[i-1]
package class071; // 乘积最大子数组 // 给你一个整数数组 nums // 请你找出数组中乘积最大的非空连续子数组 // 并返回该子数组所对应的乘积 // 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/ public class Code01_MaximumProductSubarray { // 本方法对于double类型的数组求最大累乘积也同样适用 public static int maxProduct(int[] nums) { int ans = nums[0]; for (int i = 1, min = nums[0], max = nums[0], curmin, curmax; i < nums.length; i++) { curmin = Math.min(nums[i], Math.min(min * nums[i], max * nums[i])); curmax = Math.max(nums[i], Math.max(min * nums[i], max * nums[i])); min = curmin; max = curmax; ans = Math.max(ans, max); } return ans; } }
code2 子序列累加和必须被7整除的最大累加和
// 子序列累加和必须被7整除的最大累加和
// 给定一个非负数组nums，
// 可以任意选择数字组成子序列，但是子序列的累加和必须被7整除
// 返回最大累加和
// 对数器验证
dp[i][j]：前i个数，模7余j
不选当前数：dp[i-1][j]
选当前数：dp[i-1][need]+nums[i],need=(j+7-cur)%7
package class071; // 子序列累加和必须被7整除的最大累加和 // 给定一个非负数组nums， // 可以任意选择数字组成子序列，但是子序列的累加和必须被7整除 // 返回最大累加和 // 对数器验证 public class Code02_MaxSumDividedBy7 { // 暴力方法 // 为了验证 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])); } // 正式方法 // 时间复杂度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; 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是核心 need = cur <= j ? (j - cur) : (j - cur + 7); // 或者如下这种写法也对 // need = (7 + j - cur) % 7; 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[] 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("测试结束"); } }
code3 魔法卷轴
// 魔法卷轴
// 给定一个数组nums，其中可能有正、负、0
// 每个魔法卷轴可以把nums中连续的一段全变成0
// 你希望数组整体的累加和尽可能大
// 卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴
// 请返回数组尽可能大的累加和
// 对数器验证
不使用魔法卷轴，整体累加和
使用1次魔法卷轴，prefix[i] 0~i累加和；i处不使用：prefix[i-1]+nums[i]，i处使用：之前最大前缀和
使用2次魔法卷轴，划分中点，左右各使用一次魔法卷轴
suffix[i] i~n-1累加和，i处不使用：suffix[i]+nums[i+1]，i处使用：之前最大后缀和
package class071; // 魔法卷轴 // 给定一个数组nums，其中可能有正、负、0 // 每个魔法卷轴可以把nums中连续的一段全变成0 // 你希望数组整体的累加和尽可能大 // 卷轴使不使用、使用多少随意，但一共只有2个魔法卷轴 // 请返回数组尽可能大的累加和 // 对数器验证 public class Code03_MagicScrollProbelm { // 暴力方法 // 为了测试 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; } // 正式方法 // 时间复杂度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; } // prefix[i] : 0~i范围上一定要用1次卷轴的情况下，0~i范围上整体最大累加和多少 int[] prefix = new int[n]; // 每一步的前缀和 int sum = nums[0]; // maxPresum : 之前所有前缀和的最大值 int maxPresum = Math.max(0, nums[0]); for (int i = 1; i < n; i++) { prefix[i] = Math.max(prefix[i - 1] + nums[i], maxPresum); sum += nums[i]; maxPresum = Math.max(maxPresum, sum); } // 情况二 : 必须用1次卷轴 int p2 = prefix[n - 1]; // suffix[i] : i~n-1范围上一定要用1次卷轴的情况下，i~n-1范围上整体最大累加和多少 int[] suffix = new int[n]; sum = nums[n - 1]; maxPresum = Math.max(0, sum); for (int i = n - 2; i >= 0; i--) { suffix[i] = Math.max(nums[i] + suffix[i + 1], maxPresum); sum += nums[i]; maxPresum = Math.max(maxPresum, sum); } // 情况二 : 必须用2次卷轴 int p3 = Integer.MIN_VALUE; for (int i = 1; i < n; i++) { // 枚举所有的划分点i // 0~i-1 左 // i~n-1 右 p3 = Math.max(p3, prefix[i - 1] + suffix[i]); } return Math.max(p1, Math.max(p2, p3)); } // 为了测试 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("测试结束"); } }
code4 689. 三个无重叠子数组的最大和
// 三个无重叠子数组的最大和
// 给你一个整数数组 nums 和一个整数 k
// 找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组
// 并返回这三个子数组
// 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置
// 如果有多个结果，返回字典序最小的一个
// 测试链接 : https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/
（1）sums[i]：i… k长度的sum
（2）prefix[i]：0…i范围上所有长度为k的子数组中最大sum的子数组的开头
（3）suffix[i]：i…n-1范围上所有长度为k的子数组中最大sum的子数组的开头
枚举中间的子数组
prefix[i-1] i…j (k个) suffix[j+1]
最好开头k i开头 最好开头s
package class071; // 三个无重叠子数组的最大和 // 给你一个整数数组 nums 和一个整数 k // 找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组 // 并返回这三个子数组 // 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置 // 如果有多个结果，返回字典序最小的一个 // 测试链接 : https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/ public class Code04_MaximumSum3UnoverlappingSubarrays { public static int[] maxSumOfThreeSubarrays(int[] nums, int k) { int n = nums.length; // sums[i] : 以i开头并且长度为k的子数组的累加和 int[] sums = new int[n]; for (int l = 0, r = 0, sum = 0; r < n; r++) { // l....r sum += nums[r]; if (r - l + 1 == k) { sums[l] = sum; sum -= nums[l]; l++; } } // prefix[i] : // 0~i范围上所有长度为k的子数组中，拥有最大累加和的子数组，是以什么位置开头的 int[] prefix = new int[n]; for (int l = 1, r = k; r < n; l++, r++) { if (sums[l] > sums[prefix[r - 1]]) { // 注意>，为了同样最大累加和的情况下，最小的字典序 prefix[r] = l; } else { prefix[r] = prefix[r - 1]; } } // suffix[i] : // i~n-1范围上所有长度为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, max = 0; // 0...i-1 i...j j+1...n-1 // 左 中(长度为k) 右 for (int p, s, i = k, j = 2 * k - 1, sum; j < n - k; i++, j++) { // 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 > max) { // 注意>，为了同样最大累加和的情况下，最小的字典序 max = sum; a = p; b = i; c = s; } } return new int[] { a, b, c }; } }
code5 可以翻转1次的情况下子数组最大累加和
// 可以翻转1次的情况下子数组最大累加和
// 给定一个数组nums，
// 现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整
// 比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6]
// 返回必须随意翻转1次之后，子数组的最大累加和
// 对数器验证
start[i]：i开头，往右延伸子数组的最大和
①nums[i]；②nums[i]+start[i+1]
end[i]：0…i结尾，最大累加和
①nums[i]；②nums[i]+end[i-1]
i之前最大累加和maxEnd+往右延伸子数组的最大和
ans=maxEnd+start[i]
package class071; // 可以翻转1次的情况下子数组最大累加和 // 给定一个数组nums， // 现在允许你随意选择数组连续一段进行翻转，也就是子数组逆序的调整 // 比如翻转[1,2,3,4,5,6]的[2~4]范围，得到的是[1,2,5,4,3,6] // 返回必须随意翻转1次之后，子数组的最大累加和 // 对数器验证 public class Code05_ReverseArraySubarrayMaxSum { // 暴力方法 // 为了验证 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; } // 正式方法 // 时间复杂度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--) { // nums[i] // nums[i] + start[i+1] start[i] = Math.max(nums[i], nums[i] + start[i + 1]); } int ans = start[0]; // end : 子数组必须以i-1结尾，其中的最大累加和 int end = nums[0]; // maxEnd : // 0~i-1范围上， // 子数组必须以0结尾，其中的最大累加和 // 子数组必须以1结尾，其中的最大累加和 // ... // 子数组必须以i-1结尾，其中的最大累加和 // 所有情况中，最大的那个累加和就是maxEnd int maxEnd = nums[0]; for (int i = 1; i < n; i++) { // maxend i.... // 枚举划分点 i... ans = Math.max(ans, maxEnd + start[i]); // 子数组必须以i结尾，其中的最大累加和 end = Math.max(nums[i], end + nums[i]); maxEnd = Math.max(maxEnd, end); } ans = Math.max(ans, maxEnd); 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("测试结束"); } }
code6 删掉1个数字后长度为k的子数组最大累加和
// 删掉1个数字后长度为k的子数组最大累加和
// 给定一个数组nums，求必须删除一个数字后的新数组中
// 长度为k的子数组最大累加和，删除哪个数字随意
// 对数器验证
原数组选择k+1长度的子数组
删除最小的累加和
package class071; // 删掉1个数字后长度为k的子数组最大累加和 // 给定一个数组nums，求必须删除一个数字后的新数组中 // 长度为k的子数组最大累加和，删除哪个数字随意 // 对数器验证 public class Code06_DeleteOneNumberLengthKMaxSum { // 暴力方法 // 为了测试 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; } // 正式方法 // 时间复杂度O(N) public static int maxSum2(int[] nums, int k) { int n = nums.length; if (n <= k) { return 0; } // 单调队列 : 维持窗口内最小值的更新结构，讲解054的内容 int[] window = new int[n]; int l = 0; int r = 0; // 窗口累加和 long sum = 0; int ans = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { // 单调队列 : i位置进入单调队列 while (l < r && nums[window[r - 1]] >= nums[i]) { r--; } window[r++] = i; sum += nums[i]; if (i >= k) { ans = Math.max(ans, (int) (sum - nums[window[l]])); if (window[l] == i - k) { // 单调队列 : 如果单调队列最左侧的位置过期了，从队列中弹出 l++; } sum -= nums[i - k]; } } 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("测试结束"); } }
2023-11-09 17:23:58
