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

【动态规划】24子数组系列_最长湍流子数组_C++

题目链接:最长湍流子数组


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求返回 arr 的 最大湍流子数组的长度 

由题可得:

如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是 湍流子数组;


算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义(是什么?)

这里我们需要两个dp表:

f[i]:以i位置为结尾,i位置为“上升”的最大湍流子数组的长度

g[i]:以i位置为结尾,i位置为“下降”的最大湍流子数组的长度

这种状态表示怎么来的?

1.经验+题目要求

用之前或者之后的状态,推导出dp[i][j]的值;

根据最近的最近的一步,来划分问题

经验:以i位置为结尾;

题目让我们返回 arr 的 最大湍流子数组的长度 

所以我们可以先设一个“dp表”表示以i位置为结尾,i位置最大湍流子数组的长度。

但是我们会发现:

只有一个dp表无法表示该位置的状态,状态分得还不够细(是>还是<)

所以这里我们尝试再加一个状态表示:

f[i]:以i位置为结尾,i位置为“上升”的最大湍流子数组的长度

g[i]:以i位置为结尾,i位置为“下降”的最大湍流子数组的长度

2.状态转移方程

dp[i]等于什么?

以i位置为结尾有三种情况:

只有是情况1和2时才有可能时湍流子数组;

根据我们的状态表示:

情况一(i位置为“上升”):

那么需要前面一个位置是“下降”的才满足湍流子数组;

所以此时i位置的最长湍流子数组应该是前面一个位置为“下降”的最长湍流子数组的长度+1

而“前面一个位置为“下降”的最长湍流子数组的长度”就是我们的状态表示:g[i-1]

所以:f[i]=g[i-1]+1

情况二(i位置为“下降”):

那么需要前面一个位置是“上升”的才满足湍流子数组;

所以此时i位置的最长湍流子数组应该是前面一个位置为“上升”的最长湍流子数组的长度+1

而“前面一个位置为“上升”的最长湍流子数组的长度”就是我们的状态表示:g[i-1]

所以:g[i]=f[i-1]+1

3.初始化

(保证填表的时候不越界)

我们是从第二个元素比的,所以把要把前面的都初始化为1

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:[i-1]

所以填表顺序从左往右

5.返回值

(根据题目要求和状态表示)

综上分析:

返回值为:两个表里的最大值


编写代码:

class Solution {
public:int maxTurbulenceSize(vector<int>& arr) {//1.创建dp表//2.初始化//3.填表//4.返回结果int n=arr.size();vector<int> f(n+1,1);auto g=f;int ret=1;for(int i=2;i<n+1;i++){if(arr[i-1]>arr[i-2]){f[i]=g[i-1]+1;}else if(arr[i-1]<arr[i-2]){g[i]=f[i-1]+1;}ret=max({(int)ret,g[i],f[i]});}return ret;}
};

相关文章:

【动态规划】24子数组系列_最长湍流子数组_C++

题目链接&#xff1a;最长湍流子数组 目录 题目解析&#xff1a; 算法原理 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 编写代码 题目解析&#xff1a; 题目让我们求返回 arr 的 最大湍流子数组的长度 由题可得&#xff1a; 如果比较符号在子数组中的…...

fastJson和jackson的日期数据处理

目录 1.jackson 2.fastjson 3.总结 1.jackson jackson是spring mvc默认的JSON解析方法&#xff0c;前端的数据序列化处理之后&#xff0c;后端经过反序列化处理可以直接使用实体对象进行接收。后端接口返回实体对象&#xff0c;经过序列化处理后前端可以接收并进行处理。 …...

书生·浦语大模型实战营第五节课笔记及作业

LMDeploy 大模型量化部署实践 1 大模型部署背景 1.1 模型部署及大模型特点 1.2 大模型部署挑战及方案 2 LMDeploy简介 2.1 核心功能-量化 2.2 核心功能-推理引擎TurboMind 2.1 核心功能-推理服务api server 3 动手实践及作业 按照文档LMDeploy 的量化和部署中的步骤在Intern…...

如何在CentOS 7 中基于OpenSSL 3.0 搭建Python 3.0 环境

1、OpenSSL 1.1 原因 [rootlocalhost ~]# openssl version OpenSSL 1.0.2k-fips 26 Jan 2017 [rootlocalhost ~]#通过执行openssl version可知Linux系统已经安装了OpenSSL&#xff0c;但该版本较低&#xff1b;Python 3 要求 OpenSSL版本不能低于1.1.1&#xff0c;否则安装P…...

爬虫接口获取外汇数据(汇率,外汇储备,贸易顺差,美国CPI,M2,国债利率)

akshare是一个很好用的财经数据api接口&#xff0c;完全免费&#xff01;&#xff01;和Tushare不一样。 除了我标题显示的数据外&#xff0c;他还提供各种股票数据&#xff0c;债券数据&#xff0c;外汇&#xff0c;期货&#xff0c;宏观经济&#xff0c;基金&#xff0c;银行…...

Spring Cloud和微服务架构的关系

大话Spring Cloud 在Java悠久的历史长河中(其实也就十来年)&#xff0c;有一个框架自诞生之初就成了Java企业级开发领域的弄潮儿&#xff0c;它以开放的姿态不断引领着技术改革(我们管他叫Java领域的“改革开放”)&#xff0c;它就是久经考验的企业级开发框架&#xff0c;改革…...

C++:通过ofstream写入二进制文件内容

C++:通过ifstream读取二进制文件内容_c++ ifstream 二进制读取-CSDN博客 介绍了读取二进制文件的方法。 本文介绍一下写入二进制数据到文件的方法: 1.通过write #include <fstream> #include <string> using namespace std; int main() {int data = 0x0102030…...

系统配置dns主从服务器

一、准备两台主机&#xff0c;区分主从 二、完全区域传送 1、主DNS服务器配置 #安装相关的包 [rootoula1 ~]# yum install bind -y#关闭防火墙 [rootoula1 ~]# systemctl stop firewalld [rootoula1 ~]# setenforce 0#修改配置主文件 [rootoula1 ~]# vim /etc/named.conf opt…...

【git】解决网络连接问题

ssh: connect to host github.com port 22: Connection timed out $ ssh: connect to host github.com port 22: Connection timed out fatal: Could not read from remote repository. bash: ssh:: command not found bash: fatal:: command not found无效 检查网络&#xf…...

限制API接口访问速率

文章目录 依赖注解aophelperTest 免责声明&#xff1a;本人无意侵权&#xff0c;奈何找不到原文作者&#xff0c;也找不到网址&#xff0c;于是自己记录一下&#xff0c;如果有侵权之嫌&#xff0c;请联系我删除文章 依赖 <!-- https://mvnrepository.com/artifact/com.goo…...

广东省第三届职业技能大赛“网络安全项目”B模块--数字取证解析

广东省第三届职业技能大赛“网络安全项目”B模块任务书 PS: 关注鱼影安全第一部分 网络安全事件响应第二部分 数字取证调查任务 3: 网络数据包分析取证解析:第三部分 应用程序安全:需要环境可以私信博主~PS: 关注鱼影安全 模块 B 竞赛项目试题 本文件为:广东省第三届职业技…...

全链路压力测试:现代软件工程中的重要性

全链路压力测试不仅可以确保系统在高负载下的性能和稳定性&#xff0c;还能帮助企业进行有效的风险管理和性能优化。在快速发展的互联网时代&#xff0c;全链路压力测试已成为确保软件产品质量的关键步骤。 1、测试环境搭建 测试应在与生产环境尽可能相似的环境中进行&#xff…...

【计算机网络】难点、易遗忘点总结

文章目录 1. 单工通信、半双工通信和全双工通信2. TCP的三次握手和四次挥手 1. 单工通信、半双工通信和全双工通信 主要区别在于信息传输的方向和时间安排。单工通信是指信息只能在一个方向上传输的通信方式。半双工通信允许信息在两个方向上传输&#xff0c;但在任何给定的时…...

谷达冠楠科技:抖音开网店新手小白可以卖的产品

随着互联网的发展&#xff0c;越来越多的人选择在网上开设自己的店铺。而抖音作为目前最火的短视频平台&#xff0c;也提供了开店的功能。那么&#xff0c;对于新手小白来说&#xff0c;抖音开网店可以卖哪些产品呢? 我们可以考虑的是服装类商品。抖音上有很多时尚博主&#x…...

爬虫案例—根据四大名著书名抓取并存储为文本文件

爬虫案例—根据四大名著书名抓取并存储为文本文件 诗词名句网&#xff1a;https://www.shicimingju.com 目标&#xff1a;输入四大名著的书名&#xff0c;抓取名著的全部内容&#xff0c;包括书名&#xff0c;作者&#xff0c;年代及各章节内容 诗词名句网主页如下图&#x…...

阿里云容器服务助力万兴科技 AIGC 应用加速

作者&#xff1a;子白&#xff08;顾静&#xff09; 2023 年堪称是 AIGC 元年&#xff0c;文生图领域诞生了 Stable Diffusion 项目&#xff0c;文生文领域诞生了 GPT 家族。一时间风起云涌&#xff0c;国内外许多企业投身 AIGC 创新浪潮&#xff0c;各大云厂商紧随其后纷纷推…...

STM32F103标准外设库——认识STM32(一)

个人名片&#xff1a; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的在校大学生 &#x1f42f;个人主页&#xff1a;妄北y &#x1f427;个人QQ&#xff1a;2061314755 &#x1f43b;个人邮箱&#xff1a;2061314755qq.com &#x1f989;个人WeChat&#xff1a;V…...

设计模式——1_5 享元(Flyweight)

今人不见古时月&#xff0c;今月曾经照古人 ——李白 文章目录 定义图纸一个例子&#xff1a;可以复用的样式表绘制表格降本增效&#xff1f;第一步&#xff0c;先分析 变化和不变的地方第二步&#xff0c;把变化和不变的地方拆开来第三步&#xff1a;有没有办法共享这些内容完…...

kafka系列(二)

本章承接kafka一内容&#xff0c;文章在本人博客主页都有&#xff0c;可以自行点击浏览。 幂等性 请求执行多次&#xff0c;但执行的结果是一致的。 如果&#xff0c;某个系统是不具备幂等性的&#xff0c;如果用户重复提交了某个表格&#xff0c;就可能会造成不良影响。例如…...

Ubuntu20.04安装配置OpenCV-Python库并首次执行读图

一、选择三方提供的预编译包安装&#xff1a; 可以从官网下载 OpenCV 的安装包&#xff0c;编译后使用&#xff1b;也可以直接使用第三方提供的预编译包 安装。显然后者不需要执行编译步骤&#xff0c;更便捷。选择由 PyPI 提供的 OpenCV 安装包&#xff0c;可以在 https://py…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...