当前位置: 首页 > news >正文

子序列问题集合

子序列问题

  • 删除一次得到的最大和
  • 最大子数组和
  • 最长公共子序列:
  • 最长上升子序列(要输出序列,和最大长度)
    • 1.dp
    • 2.贪心+二分
  • 导弹拦截 (最长上升/下降子序列长度)

删除一次得到的最大和

在这里插入图片描述

class Solution {
public:
/*
left[i]:以i为结尾的子数组的最大和
right[i]:以i为开始的子数组的最大和
*/int maximumSum(vector<int>& arr) {int n=arr.size();vector<int> left(n),right(n);left[0]=arr[0],right[n-1]=arr[n-1];int ans=left[0];for(int i=1;i<n;i++){left[i]=max(left[i-1],0)+arr[i];right[n-i-1]=max(right[n-i],0)+arr[n-i-1];ans=max(ans,left[i]);}for(int i=1;i<n-1;i++)ans=max(ans,left[i-1]+right[i+1]);return ans;}};

最大子数组和

在这里插入图片描述

class Solution {
public:
/*
dp[i]:以i为结尾的连续子数组的最大和
dp的子问题定义要无后效性,同时满足题意;以i为结尾,这样能够保证
在判断i位置时,dp[i-1]是连续的,这样连上i才有意义,同时当dp[i-1]已经小于0,那么前面这些子数组就没有必要加上了,其对后面可能出现的最大子数组和没有贡献
dp[n-1]不是结果,不是最大和
*/int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int> dp(n,0);dp[0]=nums[0];for(int i=1;i<n;i++){if(dp[i-1]>0)dp[i]=dp[i-1]+nums[i];elsedp[i]=nums[i];}return *max_element(dp.begin(),dp.end());}
};

最长公共子序列:

在这里插入图片描述


class Solution {
public://dfs(i,j)代表s串i前字符和t串j前个字符,的公共子序列长度//假设最长公共子序列是lcs,则当s[i]==t[j]时,那么公共子序列长度因该是+1//不同时,如果s[i]在lcs中则dfs(i,j-1),  否则t[j]在lcs中则dfs(i-1,j)//也有可能s[i]和t[j]都不在lcs中,那么就是dfs(i-1,j-1)//但是显然这个能构造出来的最长公共子序列是小于上面两个的// int dfs(string& s,string& t,int i,int j)// {//     if(i<0||j<0)return 0;//     if(s[i]==t[j])//     return dfs(s,t,i-1,j-1)+1;//     else//     return max(dfs(s,t,i-1,j),dfs(s,t,i,j-1));// }//     int longestCommonSubsequence(string s, string t) {//         return dfs(s,t,s.size()-1,t.size()-1);//     }// };这样朴素的暴搜,显然会超时,并且可以很直观的发现,这里进行了很多重复的操作//用二维数组记录之前的结果,dfs+记忆化int cache[1005][1005];int dfs(string& s, string& t, int i, int j){if (i < 0 || j < 0)return 0;int& ans = cache[i][j];if (ans != 0)return ans;//不为0说明已经确定过这个值了,不必dfsif (s[i] == t[j])return ans = dfs(s, t, i - 1, j - 1) + 1;elsereturn ans = max(dfs(s, t, i - 1, j), dfs(s, t, i, j - 1));//return dfs(s,t,i,j);}int longestCommonSubsequence(string s, string t) {return dfs(s, t, s.size() - 1, t.size() - 1);}
};

最长上升子序列(要输出序列,和最大长度)

在这里插入图片描述
两种解法:

1.dp

#include<bits/stdc++.h>
using namespace std;/*
* 最长不下降子序列
* 1.状态描述
* dp[i]:是以i为结尾的最长不下降子序列的长度
* 2.状态转移方程
* if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1);
* j是i之前的元素
*/int n, a[201], dp[201], pre[201];void reverse_print(int index)
{if (index == -1)return;reverse_print(pre[index]);cout << a[index] << " ";
}/*14
13 7 9 16 38 24 37 18 44 19 21 22 63 15*/int main()
{memset(pre, -1, sizeof(pre));cin >> n;for (int i = 0; i < n; i++){cin >> a[i];dp[i] = 1;//初始化}int maxx = 1;//最大长度至少都是1int maxIndex = 0;for (int i = 1; i < n; i++){for (int j = 0; j < i; j++){/*if (a[i] >= a[j])//如果只是求解序列长度,这样即可,但是要去找到这个序列,那还需要去记录其前驱dp[i] = max(dp[i], dp[j] + 1);maxx = max(maxx, dp[i]);*/if (a[i] >= a[j]){if (dp[j] + 1 > dp[i])//说明以j为前驱时,会得到更长的序列,此时更新pre[i]{dp[i] = dp[j] + 1;pre[i] = j;}}if (dp[i] > maxx){maxx = dp[i];maxIndex = i;}}}std::cout << "max=" << maxx << endl;reverse_print(maxIndex);return 0;
}

2.贪心+二分

/*解法一:贪心+二分 */
class Solution {
public:int low_bound(vector<int>& arr, int key)//去找一个最小的大于key的{int left = 0, right = arr.size();while (left < right){int mid = (left + right) / 2;if (arr[mid] < key)left = mid + 1;else if (arr[mid] > key)//当mid大于key时,不是让right=mid-1;因为有可能此时的mid就是最小的大于key的right = mid;}return right;}int lengthOfLIS(vector<int>& nums) {vector<int> ret;//ret[i]表示长度为i+1的子序列的最小值/*我尽可能让这个子序列的末尾元素小,这样后面更多的元素才可能加入*/ret.push_back(nums[0]);//一个必然升序for (int i = 1, k = 1; i < nums.size(); i++)//k是此时ret中有多少个元素,作为下标使用k-1{if (nums[i] > ret[k - 1])//大于ret的结尾,ret的结尾是ret中的最大的,直接加入{ret.push_back(nums[i]);k++;}else if (nums[i] < ret[k - 1])//遇到小于,则往前去找一个最小的并且大于的num[i]的ret{int pos = low_bound(ret, nums[i]);//这里使用二分,提高效率//cout << "pos=" << pos << endl;//if (ret[pos] == nums[i])continue;ret[pos] = nums[i];}}return ret.size();}
};

导弹拦截 (最长上升/下降子序列长度)

在这里插入图片描述

/*
* 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。389 207 155 300 299 170 158 656
2其实就是去求这个序列的最长上升子序列的长度,和最长下降子序列的长度
*/#include<bits/stdc++.h>
using namespace std;int n = 1, a[1001], dp_up[1001], dp_down[1001];
int main()
{while (cin >> a[n]){dp_up[n] = dp_down[n] = 1;n++;}n--;int max_down = 1, max_up = 1;for (int i = 2; i <= n; i++){for (int j = 1; j < i; j++){if (a[i] > a[j])dp_up[i] = max(dp_up[i], dp_up[j] + 1);if (a[i] <= a[j])dp_down[i] = max(dp_down[i], dp_down[j] + 1);}max_down = max(max_down, dp_down[i]);max_up = max(max_up, dp_up[i]);}cout << max_down << endl << max_up << endl;return 0;
}

相关文章:

子序列问题集合

子序列问题 删除一次得到的最大和最大子数组和最长公共子序列&#xff1a;最长上升子序列&#xff08;要输出序列&#xff0c;和最大长度&#xff09;1.dp2.贪心二分 导弹拦截 &#xff08;最长上升/下降子序列长度&#xff09; 删除一次得到的最大和 class Solution { public:…...

idea中提示:error has occurred, please check your installation and try again

目录 报错原因解决总结 报错 idea中提示&#xff1a;error has occurred, please check your installation and try again 原因 1.起初我是把一个运行正常的java程序&#xff0c;放到了src下&#xff0c;新建的一个包&#xff08;包名为java.first&#xff09;中&#xff0c…...

MySQL - 关于约束类型和作用的介绍

约束的概念&#xff1a;约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。 约束的作用&#xff1a;用于保证数据库中数据的正确性、完整性和一致性。 约束分类&#xff1a; 约束类型作用关键字非空约束限制该字段的数据不能为nullnot null唯一约束保证该…...

【2023集创赛】芯原杯一等奖作品:基于芯原DSP核的智能语音SoC设计

本文为2023年第七届全国大学生集成电路创新创业大赛&#xff08;“集创赛”&#xff09;芯原杯一等奖作品分享&#xff0c;参加极术社区的【有奖征集】分享你的2023集创赛作品&#xff0c;秀出作品风采&#xff0c;分享2023集创赛作品扩大影响力&#xff0c;更有丰富电子礼品等…...

代理IP与Socks5代理在跨界电商、爬虫、游戏和网络安全中的应用

在数字化时代&#xff0c;网络工程师们需要不断应对各种技术挑战&#xff0c;以满足跨界电商、爬虫、游戏和网络安全领域的需求。本文将聚焦于代理IP和Socks5代理&#xff0c;探讨它们在这些领域中的重要应用和影响。 1. 代理IP&#xff1a;跨越地域的电商战略 跨界电商已经成…...

DDS信号发生器Verilog波形发生器FPGA

名称&#xff1a;DDS信号发生器Verilog波形发生器 软件&#xff1a;Quartus 语言&#xff1a;Verilog 要求&#xff1a; 1.可产生正弦波&#xff0c;锯齿波&#xff0c;三角波&#xff0c;方波4种波形&#xff0c;频率可调 2.具有波形选择、起动、停止功能。 代码下载&…...

基于springboot实现二手交易平台管理系统演示【项目源码】分享

基于springboot实现二手交易平台管理系统演示 java简介 Java语言是在二十世纪末由Sun公司发布的&#xff0c;而且公开源代码&#xff0c;这一优点吸引了许多世界各地优秀的编程爱好者&#xff0c;也使得他们开发出当时一款又一款经典好玩的小游戏。Java语言是纯面向对象语言之…...

一个链接分享自制的产品图册

​在商业中我们都需要一本产品册展现自家的产品特点&#xff0c;方便更多的人群挑选产品。但是纸质版的消费量最大&#xff0c;还不好存放和管理。不妨试试制作一本电子版的产品图册&#xff0c;无论是新手还是有经验者都能轻松上手 接下来给大家分享这款网站---FLBOOK在线制作…...

2023工博会 | 上海添力网络营销公司 | 助力工业品线上推广

2023年9月23日&#xff0c;为期五天的工博会正式落下帷幕。本届工博会不仅有数量&#xff0c;更加有质量&#xff0c;国内外企业纷纷拿出看家本领&#xff0c;围绕着“绿色低碳”、“数字化转型”、“数字经济”、“科技创新”、“智能制造”等主题进行推陈出新。 本次工博会也…...

React实现多图片预览功能、预览图上下张切换(实战示例)

前言 在React项目中&#xff0c;展示和预览多张图片是一种常见的需求。本篇帖子将介绍如何使用React和antd库来实现这一功能&#xff0c;并探讨如何在预览模态框中切换到前一张或后一张图片。 背景 我们将以一个OCR图像列表展示的示例来演示代码的运用。假设我们有一个OCR系…...

【NLP的Python库(04/4)】:Flair

一、说明 Flair是一个现代的NLP库。从文本处理到文档语义&#xff0c;支持所有核心 NLP 任务。Flair使用现代转换器神经网络模型来完成多项任务&#xff0c;并结合了其他Python库&#xff0c;可以选择特定的模型。其清晰的API和注释文本的数据结构&#xff0c;以及多语言支持&a…...

Vue框架学习大纲

Vue.js 是一个构建用户界面的框架&#xff0c;尤其是单页面应用。以下是一些主要基于 Vue 2.x 的版本必须了解的 Vue.js基本知识点和特性&#xff1a; Vue 实例: 创建一个 Vue 实例是开始使用 Vue 的第一步。 var vm new Vue({// 选项 });数据绑定: Vue 提供了非常直观的数据绑…...

利用PPT导出一张高清图的方法,office与WPS只需要使用一个即可,我使用的是office。

利用PPT导出一张高清图的方法&#xff0c;office与WPS只需要使用一个即可&#xff0c;我使用的是office。 1&#xff0c;PPT的功能拓展来解决导出高清图片方法1.1&#xff0c;PPT功能拓展—>安装插件&#xff1a; 2&#xff0c;各种方法导出图片效果显示&#xff1a;2.1&…...

2023年【四川省安全员B证】最新解析及四川省安全员B证模拟考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 四川省安全员B证最新解析考前必练&#xff01;安全生产模拟考试一点通每个月更新四川省安全员B证模拟考试题目及答案&#xff01;多做几遍&#xff0c;其实通过四川省安全员B证模拟考试题很简单。 1、【多选题】5.5kW…...

某瑞集团安全技术研发岗位面试

本文由掌控安全学院 - sbhglqy 投稿 一、自我介绍 阿吧阿吧&#xff0c;不多说 二、就ctf比赛经历方面提些问题 面试官&#xff1a;ctf打了多久了 我&#xff1a;两三年了。 面试官&#xff1a;得过什么奖项没有 我&#xff1a;本科的时候得过一个校一等奖。 面试官&#x…...

学习笔记|ADC反推电源电压|扫描按键(长按循环触发)|课设级实战练习|STC32G单片机视频开发教程(冲哥)|第十八集:ADC实战

文章目录 1.ADC反推电源电压测出Vref引脚电压的意义?手册示例代码分析复写手册代码Tips&#xff1a;乘除法与移位关系为什么4096后面还有L 2.ADC扫描按键(长按循环触发)长按触发的实现 3.实战小练1.初始状态显示 00 - 00 - 00&#xff0c;分别作为时&#xff0c;分&#xff0c…...

2020 款凯迪拉克 XT5 车发动机加速异响

故障现象 一辆2020款凯迪拉克XT5车&#xff0c;搭载LSY发动机&#xff0c;累计行驶里程约为8万km。车主反映&#xff0c;加速时发动机有明显异响。 故障诊断 接车后试车&#xff0c;起动发动机&#xff0c;发动机怠速运转平稳&#xff1b;打开发动机室盖&#xff0c;能够听到轻…...

【AI视野·今日CV 计算机视觉论文速览 第255期】Wed, 27 Sep 2023

AI视野今日CS.CV 计算机视觉论文速览 Wed, 27 Sep 2023 (showing first 100 of 103 entries) Totally 100 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers Generating Visual Scenes from Touch Authors Fengyu Yang, Jiacheng Zhang, Andre…...

Java应用生产Full GC或者OOM问题如何定位

1 引言 生产应用服务频繁Full GC却无法释放内存&#xff0c;甚至可能OOM&#xff0c;这种情况很有可能是内存泄露或者堆内存分配不足&#xff0c;此时需要dump堆信息来定位问题&#xff0c;查看是哪些地方内存泄漏。 Dump文件也称为内存转储文件或内存快照文件&#xff0c;是…...

Data processing flow

1. 找出第一年的address&#xff0c;有lat和long&#xff0c;自动生成 csv_log_lat_county.ipynb import csv from geopy.geocoders import Nominatim from geopy.exc import GeocoderTimedOutgeolocator Nominatim(user_agent"my-app") data_csv r"D:/year…...

CAP理论与BASE理论

分布式领域CAP理论&#xff1a; Consistency(一致性), 数据一致更新&#xff0c;所有数据变动都是同步的Availability(可用性), 好的响应性能Partition tolerance(分区容错性) 可靠性定理&#xff1a;任何分布式系统只可同时满足二点&#xff0c;没法三者兼顾。忠告&#xff1…...

DRM全解析 —— ADD_FB2(3)

接前一篇文章&#xff1a;DRM全解析 —— ADD_FB2&#xff08;2&#xff09; 本文参考以下博文&#xff1a; DRM驱动&#xff08;四&#xff09;之ADD_FB 特此致谢&#xff01; 上一回围绕libdrm与DRM在Linux内核中的接口&#xff1a; DRM_IOCTL_DEF(DRM_IOCTL_MODE_ADDFB2,…...

【Java】SpringMVC ResponseBodyAdvice详解

目录 1. ResponseBodyAdvice 2. supports方法 3. beforeBodyWrite方法 4. 实践 1. ResponseBodyAdvice Spring MVC的ResponseBodyAdvice是Spring 4.1版本中引入的一个接口&#xff0c;它允许在Controller控制器中ResponseBody修饰的方法或ResponseEntity执行之后&#xff…...

python常见面试题五

解释 Python 中的列表推导式 (list comprehension)。 答&#xff1a;列表推导式是一种创建新列表的简洁方式。它可以在一行代码中通过对一个可迭代对象应用表达式和条件来生成新的列表。 解释 Python 中的时间复杂度和空间复杂度。 答&#xff1a;时间复杂度衡量算法运行时间的…...

SpringBoot结合Vue.js+axios框架实现增删改查功能+网页端实时显示数据库数据(包括删除多条数据)

本文适用对象&#xff1a;已有基础的同学&#xff0c;知道基础的SpringBoot配置和Vue操作。 在此基础上本文实现基于SpringBoot和Vue.js基础上的增删改查和数据回显、刷新等。 一、实时显示数据库数据 实现步骤&#xff1a; 第1步&#xff1a;编写动态请求响应类&#xff1a…...

曙光亮相工博会,发布首款国产高端工业实时仿真计算系统

9月19日-23日&#xff0c;中科曙光亮相第23届中国国际工业博览会&#xff0c;并受邀于主论坛发表主题演讲&#xff0c;在工业权威会议上展示曙光领先的工业数字化技术与实践成果。展会期间&#xff0c;曙光重磅发布首款国产工业实时仿真计算系统&#xff0c;并展出多项工业数字…...

「大数据-2.0」安装Hadoop和部署HDFS集群

目录 一、下载Hadoop安装包 二、安装Hadoop 0. 安装Hadoop前的必要准备 1. 以root用户登录主节点虚拟机 2. 上传Hadoop安装包到主节点 3. 解压缩安装包到/export/server/目录中 4. 构建软链接 三、部署HDFS集群 0. 集群部署规划 1. 进入hadoop安装包内 2 进入etc目录下的hadoop…...

文档在线预览word、pdf、excel文件转html以实现文档在线预览

目录 一、前言 1、aspose2 、poi pdfbox3 spire二、将文件转换成html字符串 1、将word文件转成html字符串 1.1 使用aspose1.2 使用poi1.3 使用spire2、将pdf文件转成html字符串 2.1 使用aspose2.2 使用 poi pbfbox2.3 使用spire3、将excel文件转成html字符串 3.1 使用aspose…...

FFmpeg视音频分离器----向雷神学习

雷神博客地址&#xff1a;https://blog.csdn.net/leixiaohua1020/article/details/39767055 本程序可以将封装格式中的视频码流数据和音频码流数据分离出来。 在该例子中&#xff0c; 将FLV的文件分离得到H.264视频码流文件和MP3 音频码流文件。 注意&#xff1a; 这个是简化版…...

CentOS 8开启bbr

CentOS 8 默认内核版本为 4.18.x&#xff0c;内核版本高于4.9 就可以直接开启 BBR&#xff0c;所以CentOS 8 启用BBR非常简单不需要再去升级内核。 开启bbr echo "net.core.default_qdiscfq" >> /etc/sysctl.conf echo "net.ipv4.tcp_congestion_contro…...

北京建筑大学/seo营销技巧

登录1. 打开A网站进行登录&#xff1b;2. 检测Login服务器是否可用&#xff1b;3. 如果Login服务器可用&#xff0c;检测发现Login服务器Session未创建&#xff1b;4. 重定向到A网站的页面&#xff0c;接受Login服务器传来的Key和UID组成的类序列化后的…...

网站制作百度资源/国内真正的永久免费砖石

如何将c&#xff1a;forEach标记的循环索引附加到struts select / text标记的属性&#xff1f;例如.抛出以下错误org.apache.struts.taglib.html.SelectTag.calculateMatchValues(SelectTag.java:246)中的javax.servlet.jsp.JspException现在,当我在< html&#xff1a;selec…...

网站如何收录/网红推广团队去哪里找

MATLAB同其他高级语言一致&#xff0c;有三种基本程序结构&#xff1a; 顺序结构&#xff1b;选择结构&#xff1b;循环结构 MATLAB流程控制语句主要有&#xff1a; ForWhileif-else-endswitch-case 常用命令&#xff1a; BreakContinue以及matlab特有的try命令&#xff0…...

高端网站制作费用/网站软件免费下载

docker-compose.yml version: "2" services:eid-service:# 指定容器名称container_name: xxx-service# 重启机制restart: always# hub地址&#xff0c;image版本image: hub.xxx.cn/xxx-service/xxx-service:latestvolumes:# 本地jar包路径- /opt/service/1.5/xxx-se…...

广州铁路投资建设集团网站/服务推广软文范例

i2c-tools i2cdetect 检测在系统上的i2c总线&#xff0c;例如&#xff1a; i2cdetect -l 检测挂载在i2c总线上器件&#xff0c;例如&#xff1a; i2cdetect -r -y 0 &#xff08;检测i2c-0上的挂载情况&#xff09; i2cdump 查看器件所有寄存器的值&#xff0c;例如&#xff1a…...

国内著名平面设计师的个人网站/seo薪资seo

前言我于2020年开始接触、使用Vercel(ZEIT)的&#xff0c;要是我能早点知道的话&#xff0c;我也不会煞费苦心去优化Github上的个人博客的加载速度问题&#xff0c;当然国内也有类似Github的代码托管网站&#xff0c;如Gitee(码云)&#xff0c;Coding(被腾讯收购&#xff0c;还…...