class070 子数组最大累加和问题与扩展-上【算法】
code1 53. 最大子数组和
// 累加和最大子数组和
// 给你一个整数数组 nums
// 请你找出一个具有最大累加和的非空子数组
// 返回其最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-subarray/
dp[i]：以i结尾的子数组[…i]的最大累加和
(1) nums[i] (2) dp[i-1]+nums[i] 二者取最大的
返回Max(dp[…])
code1 动态规划
code2 空间压缩
package class070;
// 子数组最大累加和
// 给你一个整数数组 nums
// 返回非空子数组的最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-subarray/
public class Code01_MaximumSubarray {
// 动态规划
public static int maxSubArray1(int[] nums) {
int n = nums.length;
// dp[i] : 子数组必须以i位置的数做结尾，往左能延伸出来的最大累加和
int[] dp = new int[n];
dp[0] = nums[0];
int ans = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
ans = Math.max(ans, dp[i]);
}
return ans;
}
// 空间压缩
public static int maxSubArray2(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;
}
// 如下代码为附加问题的实现
// 子数组中找到拥有最大累加和的子数组
// 并返回如下三个信息:
// 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) {
sum = Integer.MIN_VALUE;
for (int l = 0, r = 0, pre = Integer.MIN_VALUE; r < nums.length; r++) {
if (pre >= 0) {
// 吸收前面的累加和有利可图
// 那就不换开头
pre += nums[r];
} else {
// 吸收前面的累加和已经无利可图
// 那就换开头
pre = nums[r];
l = r;
}
if (pre > sum) {
sum = pre;
left = l;
right = r;
}
}
}
}code2 198. 打家劫舍
// 数组中不能选相邻元素的最大累加和
// 给定一个数组，可以随意选择数字
// 但是不能选择相邻的数字，返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber/
dp[i]：表示[0…i]这个范围上不能选相邻元素的最大累加和
- 不要[i]，dp[i-1]
- 要[i] a.nums[i] b.dp[i-2]+nums[i]
code1 动态规划
code2 空间压缩
package class070;
// 数组中不能选相邻元素的最大累加和
// 给定一个数组，可以随意选择数字
// 但是不能选择相邻的数字，返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber/
public class Code02_HouseRobber {
// 动态规划
public static 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] : nums[0...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 - 1], Math.max(nums[i], dp[i - 2] + nums[i]));
}
return dp[n - 1];
}
// 空间压缩
public static 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, cur; i < n; i++) {
cur = Math.max(pre, Math.max(nums[i], prepre + nums[i]));
prepre = pre;
pre = cur;
}
return pre;
}
}code3 918. 环形子数组的最大和
// 环形数组的子数组最大累加和
// 给定一个数组nums，长度为n
// nums是一个环形数组，下标0和下标n-1是连在一起的
// 返回环形数组中，子数组最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/
(1) 答案不被隔断，同1普通数组，最大累加和maxSum
(2) 答案被隔断，整体累加和all-最小累加和minSum
两者取较大即为答案
package class070;
// 环形数组的子数组最大累加和
// 给定一个数组nums，长度为n
// nums是一个环形数组，下标0和下标n-1是连在一起的
// 返回环形数组中，子数组最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/
public class Code03_MaximumSumCircularSubarray {
public static int maxSubarraySumCircular(int[] nums) {
int n = nums.length, all = nums[0], maxsum = nums[0], minsum = nums[0];
for (int i = 1, maxpre = nums[0], minpre = nums[0]; i < n; i++) {
all += nums[i];
maxpre = Math.max(nums[i], nums[i] + maxpre);
maxsum = Math.max(maxsum, maxpre);
minpre = Math.min(nums[i], nums[i] + minpre);
minsum = Math.min(minsum, minpre);
}
// 1) maxsum
// 2) all - minsum
return all == minsum ? maxsum : Math.max(maxsum, all - minsum);
}
}code4 213. 打家劫舍 II
// 环形数组中不能选相邻元素的最大累加和
// 给定一个数组nums，长度为n
// nums是一个环形数组，下标0和下标n-1是连在一起的
// 可以随意选择数字，但是不能选择相邻的数字
// 返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber-ii/
思路：
不要[0]位置 [1…n-1]
要[0]位置 nums[0] + [2…n-2]
package class070;
// 环形数组中不能选相邻元素的最大累加和
// 给定一个数组nums，长度为n
// nums是一个环形数组，下标0和下标n-1是连在一起的
// 可以随意选择数字，但是不能选择相邻的数字
// 返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber-ii/
public class Code04_HouseRobberII {
public static int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(best(nums, 1, n - 1), nums[0] + best(nums, 2, n - 2));
}
// nums[l....r]范围上，没有环形的概念
// 返回 : 可以随意选择数字，但不能选择相邻数字的情况下，最大累加和
public static 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[r]);
}
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] + Math.max(0, prepre));
prepre = pre;
pre = cur;
}
return pre;
}
}code5 2560. 打家劫舍 IV
// 打家劫舍 IV
// 沿街有一排连续的房屋。每间房屋内都藏有一定的现金
// 现在有一位小偷计划从这些房屋中窃取现金
// 由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
// 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
// 给你一个整数数组 nums 表示每间房屋存放的现金金额
// 第i间房屋中放有nums[i]的钱数
// 另给你一个整数k，表示小偷需要窃取至少 k 间房屋
// 返回小偷需要的最小窃取能力值
// 测试链接 : https://leetcode.cn/problems/house-robber-iv/
二分答案法
能力[min,max]有单调性
布尔函数判断能力值给定，是否能偷够k间
dp[i]：[0…i]范围上不偷相邻房间并且有能力要求的最大间数
不偷[i]，dp[i-1]
能力大于[i]，偷[i] dp[i-2]+1
偷不了[i] dp[i-2]
贪心优化：
能偷就偷，偷了就跳过，
尽早偷，留下更大的区间
code1 动态规划
code2 空间压缩
code3 贪心优化
package class070;
// 打家劫舍 IV
// 沿街有一排连续的房屋。每间房屋内都藏有一定的现金
// 现在有一位小偷计划从这些房屋中窃取现金
// 由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
// 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
// 给你一个整数数组 nums 表示每间房屋存放的现金金额
// 第i间房屋中放有nums[i]的钱数
// 另给你一个整数k，表示小偷需要窃取至少 k 间房屋
// 返回小偷需要的最小窃取能力值
// 测试链接 : https://leetcode.cn/problems/house-robber-iv/
public class Code05_HouseRobberIV {
public static int minCapability(int[] nums, int k) {
int n = nums.length, l = nums[0], r = nums[0];
for (int i = 1; i < n; i++) {
l = Math.min(l, nums[i]);
r = Math.max(r, nums[i]);
}
// l....r
int m, ans = 0;
while (l <= r) {
m = (l + r) / 2;
if (mostRob1(nums, n, m) >= k) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
// 盗贼能力为ability时
// 返回盗贼最多能窃取多少间房屋
// 注意限制 : 不能窃取相邻房屋
public static int mostRob1(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[] dp = new int[n];
dp[0] = nums[0] <= ability ? 1 : 0;
dp[1] = (nums[0] <= ability || 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];
}
// 继续空间压缩优化
public static int mostRob2(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, (nums[i] <= ability ? 1 : 0) + prepre);
prepre = pre;
pre = cur;
}
return pre;
}
// 继续贪心优化
public static int mostRob3(int[] nums, int n, int ability) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (nums[i] <= ability) {
ans++;
i++;
}
}
return ans;
}
}code6 面试题 17.24. 最大子矩阵
// 子矩阵最大累加和问题
// 给定一个二维数组grid，找到其中子矩阵的最大累加和
// 返回拥有最大累加和的子矩阵左上角和右下角坐标
// 如果有多个子矩阵都有最大累加和，返回哪一个都可以
// 测试链接 : https://leetcode.cn/problems/max-submatrix-lcci/
package class070;
import java.util.Arrays;
// 子矩阵最大累加和问题
// 给定一个二维数组grid，找到其中子矩阵的最大累加和
// 返回拥有最大累加和的子矩阵左上角和右下角坐标
// 如果有多个子矩阵都有最大累加和，返回哪一个都可以
// 测试链接 : https://leetcode.cn/problems/max-submatrix-lcci/
public class Code06_MaximumSubmatrix {
// 如果行和列的规模都是n，时间复杂度O(n^3)，最优解了
public static int[] getMaxMatrix(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 };
}
}