class070 子数组最大累加和问题与扩展-上【算法】

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]这个范围上不能选相邻元素的最大累加和

  1. 不要[i]，dp[i-1]
  2. 要[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 };
	}

}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/233141.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Aloha 机械臂的学习记录2——AWE：AWE + ACT

Aloha 机械臂的学习记录2——AWE：AWE + ACT

继续下一个阶段&#xff1a; Train policy python act/imitate_episodes.py \ --task_name [TASK] \ --ckpt_dir data/outputs/act_ckpt/[TASK]_waypoint \ --policy_class ACT --kl_weight 10 --chunk_size 50 --hidden_dim 512 --batch_size 8 --dim_feedforward 3200 \ --n…
阅读更多...
如何轻松恢复 Windows 中删除的文件夹

如何轻松恢复 Windows 中删除的文件夹

我们都曾经历过这样的事&#xff0c;而且我们中的大多数人可能很快就会再次这样做。我们讨论的是在 Windows 中按“Delete”或“ShiftDelete”键意外删除重要文件夹的情况。 如果您刚刚按下删除键且未超过 30 天&#xff0c;或者尚未清空回收站&#xff0c;则可以恢复文件夹。…
阅读更多...
uniapp获取wifi连接状态

uniapp获取wifi连接状态

当使用Uniapp开发移动应用时&#xff0c;我们经常需要获取设备的连接状态&#xff0c;特别是WiFi连接状态。下面是一个简短的关于在Uniapp中获取WiFi连接状态的博客&#xff1a; 在Uniapp中&#xff0c;要获取设备的WiFi连接状态&#xff0c;我们可以利用uni.getNetworkType接…
阅读更多...
统信UOS_麒麟KYLINOS上跨架构下载离线软件包

统信UOS_麒麟KYLINOS上跨架构下载离线软件包

原文链接&#xff1a;统信UOS/麒麟KYLINOS上跨架构下载离线软件包 hello&#xff0c;大家好啊&#xff0c;今天给大家带来一篇在统信UOS/麒麟KYLINOS上跨架构下载离线软件包的实用教程。在我们的日常工作中&#xff0c;可能会遇到这样的情况&#xff1a;需要为不同架构的设备下…
阅读更多...
键盘打字盲打练习系列之反复练习——3

键盘打字盲打练习系列之反复练习——3

一.欢迎来到我的酒馆 盲打&#xff0c;反复练习&#xff01; 目录 一.欢迎来到我的酒馆二.数字&符号键位指法1.数字键位指法2.符号键位指法 三.反复练习 二.数字&符号键位指法 前面的一个章节重点介绍了主键盘区字母键位的指法&#xff1a;基准键位指法、" QWERTY…
阅读更多...
WireShark监控浏览器登录过程网络请求

WireShark监控浏览器登录过程网络请求

软件开发中经常前后端扯皮。一种是用Chrome浏览器的开发者工具 来看网络交互&#xff0c;但是前提是 网络端口的确是通的。 WireShark工作在更低层。 这个工具最大的好处&#xff0c;大家别扯皮&#xff0c;看网络底层的log&#xff0c;到底 你的端口开没开&#xff0c; 数据…
阅读更多...
idea中run和debug是灰色的

idea中run和debug是灰色的

【现象】idea中run和debug是灰色的 点击 旁边的Add Configuration…一看都是空白 【解决方法】&#xff1a; npm点开之后 【结果】
阅读更多...
【Java+MySQL】前后端连接小白教程

【Java+MySQL】前后端连接小白教程

目录 &#x1f36d;【IntelliJ IDEA】操作 &#x1f36d;1. 连接MySQL数据库 &#x1f308;1.1 错误解决 &#x1f36d;2. 操作MySQL数据库 &#x1f308;2.1 双击查看表数据 &#x1f308;2.2 编写SQL脚本 &#x1f36d;【IntelliJ IDEA】 IntelliJ IDEA是由JetBrains公司…
阅读更多...
js 复制粘贴板，当clipboardjs 不好使怎么办？

js 复制粘贴板，当clipboardjs 不好使怎么办？

最近项目中做一个很常见的复制粘贴的功能耽误了比较长的时间特此记录&#xff0c;在往常这个功能直接用 clipboard 做就行了&#xff0c;但是这次却发现复制功能不好使了&#xff0c;虽然走了复制成功的回调&#xff0c;但是粘贴板并没有复制的内容。代码如下 <div v-for&q…
阅读更多...
虚拟机安装 hyper—v 沙盒

虚拟机安装 hyper—v 沙盒

一、下载系统镜像 1、确认电脑内存在8G及以上并提前准备完整的系统镜像 安装Hyper-V并重启电脑后打开程序选择虚拟机 选择安装位置并设置保留第一代的虚拟参数即可开始分配内存&#xff0c;根据自己的需求进行设置 右键虚拟机启动并开始运行&#xff0c;进行镜像系统的安装便完…
阅读更多...
初识人工智能，一文读懂强化学习的知识文集(5)

初识人工智能，一文读懂强化学习的知识文集(5)

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…
阅读更多...
Python之html2text，清晰解读HTML内容！

Python之html2text，清晰解读HTML内容！

更多Python学习内容&#xff1a;ipengtao.com 大家好&#xff0c;我是彭涛&#xff0c;今天为大家分享 Python之html2text&#xff0c;清晰解读HTML内容&#xff0c;全文3900字&#xff0c;阅读大约10分钟。 HTML是Web开发中常见的标记语言&#xff0c;但有时我们需要将HTML内容…
阅读更多...
【MyBatis系列】MyBatis字符串问题

【MyBatis系列】MyBatis字符串问题

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
软件设计师——计算机组成原理（二）

软件设计师——计算机组成原理（二）

&#x1f4d1;前言 本文主要是【计算机组成原理】——软件设计师——计算机组成原理的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 …
阅读更多...
ffmpeg之ffprobe.c源码分析一---大流程及核心代码分析

ffmpeg之ffprobe.c源码分析一---大流程及核心代码分析

文章目录 前言为什么学习ffprobe源码源码调试main()函数重要流程函数分析open_input_file函数分析avformat_match_stream_specifier函数分析read_packets函数分析本篇文章带你打通ffprobe源码的脉络。 关注公众号免费看： 前言 注：本文章全凭个人经验以及平时学习所记录，由…
阅读更多...
Git merge 与 Git rebase 与 Git fetch

Git merge 与 Git rebase 与 Git fetch

Git merge 与 Git rebase 看这个图就行了 git merge、git rebase 和 git fetch 是 Git 中的三个不同的命令&#xff0c;它们分别用于不同的目的。以下是它们的主要区别&#xff1a; git merge&#xff08;合并&#xff09;&#xff1a; 用途&#xff1a; 用于将一个分支的更改…
阅读更多...
optional

optional

参考资料&#xff1a; Java8 Optional用法和最佳实践 - 掘金 一、背景 根据Oracle文档&#xff0c;Optional是一个容器对象&#xff0c;可以包含也可以不包含非null值。Optional在Java 8中引入&#xff0c;目的是解决 NullPointerExceptions的问题。本质上&#xff0c;Optio…
阅读更多...
【C语言】内联函数

【C语言】内联函数

一、内联函数 在C语言中&#xff0c;内联函数&#xff08;Inline function&#xff09;是一种代码优化技术&#xff0c;它的目的是减少函数调用的开销。内联函数通知编译器在每个函数调用的位置插入函数的实际代码&#xff0c;而不是进行传统的函数调用。这避免了调用函数时的…
阅读更多...
什么是特征图？

什么是特征图？

在卷积神经网络&#xff08;CNN&#xff09;中&#xff0c;特征图是在传递给卷积层的图像上发生卷积操作后卷积层的输出。 特征图是如何形成的&#xff1f; 在上面的插图中&#xff0c;我们可以看到特征图是如何从提供的输入图像中形成的。 要发送到卷积层的图像是一个包含像…
阅读更多...
讲解把一个文件夹里面的内容复制到另一个文件夹中的操作

讲解把一个文件夹里面的内容复制到另一个文件夹中的操作

&#x1f38a;专栏【Java小练习】 &#x1f354;喜欢的诗句&#xff1a;天行健&#xff0c;君子以自强不息。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f354;需求⭐思路✨代码✨效果 &#x1f384;如果要复制…
阅读更多...
最新文章

Copyright @ 2022~2023