「动态规划」如何求最长摆动子序列的长度?

376. 摆动序列icon-default.png?t=N7T8https://leetcode.cn/problems/wiggle-subsequence/description/

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如,[1, 7, 4, 9, 2, 5]是一个摆动序列,因为差值(6, -3, 5, -7, 3)是正负交替出现的。相反,[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。子序列可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。给你一个整数数组nums,返回nums中作为摆动序列的最长子序列的长度。

  1. 输入:nums = [1,7,4,9,2,5],输出:6,解释:整个序列均为摆动序列,各元素之间的差值为(6, -3, 5, -7, 3)。
  2. 输入:nums = [1,17,5,10,13,15,10,5,16,8],输出:7,解释:这个序列包含几个长度为7摆动序列。其中一个是[1, 17, 10, 13, 10, 16, 8],各元素之间的差值为(16, -7, 3, -3, 6, -8)。
  3. 输入:nums = [1,2,3,4,5,6,7,8,9],输出:2。

提示:1 <= nums.length <= 1000,0 <= nums[i] <= 1000。

进阶:你能否用O(n)的时间复杂度完成此题?


我们用动态规划的思想来解决这个问题。

确定状态表示:根据经验和题目要求,为了方便推导状态转移方程,我们定义如下的状态表示:

  • 用f[i]表示:所有以i位置为结尾的最后呈现上升趋势的子序列中,最长的摆动序列的长度
  • 用g[i]表示:所有以i位置为结尾的最后呈现下降趋势的子序列中,最长的摆动序列的长度

推导状态转移方程:考虑f[i]。我们把以i位置为结尾的子序列分为2类:长度为1的子序列,长度大于1的子序列。如果子序列的长度是1,那么这个子序列是摆动序列。下面我们考虑长度大于1的子序列。

如果以i位置为结尾的子序列的长度大于1,我们可以继续细分为:i位置元素的前面是i - 1位置元素的子序列,i位置元素的前面是i - 2位置元素的子序列,i位置元素的前面是i - 3位置元素的子序列,……,i位置元素的前面是0位置元素的子序列。也就是说,如果子序列中,i位置元素的前面是j位置元素,那么j的范围是[0, i - 1]。

对于每一个j,如果nums[j] < nums[i],那么这个序列最后呈现上升趋势。若想要这个序列是摆动序列,就要找到以j位置为结尾的最后呈现下降趋势的摆动序列,在后面添加上nums[i],就是以i位置为结尾的最后呈现上升趋势的摆动序列。若想要这个摆动序列尽可能得长,那么以j位置为结尾的最后呈现下降趋势的摆动序列就要尽可能得长,根据状态表示,以j位置为结尾的最后呈现下降趋势的摆动序列的最长长度是g[j]。所以,以i位置为结尾的最后呈现上升趋势的摆动序列的最长长度是g[j] + 1。

我们来梳理一下。f[i]应该取:「1」和「所有的满足0 <= j < i并且nums[j] < nums[i]的j中,g[j] + 1的最大值」的较大值。为了实现这个逻辑,我们可以把f表的值全部初始化为1,接着让i > 0时的f[i]取:所有的满足0 <= j < i并且nums[j] < nums[i]的j中,g[j] + 1的最大值

同理,g[i]应该取:「1」和「所有的满足0 <= j < i并且nums[j] > nums[i]的j中,f[j] + 1的最大值」的较大值。为了实现这个逻辑,我们可以把g表的值全部初始化为1,接着让i > 0时的g[i]取:所有的满足0 <= j < i并且nums[j] > nums[i]的j中,f[j] + 1的最大值

填表顺序:根据状态转移方程,显然应从左往右同时填2个表

返回值:根据状态表示,我们应返回f表和g表的所有值中的最大值

细节问题:f表和g表的规模和nums相同,均为1 x n

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();

        // 创建dp表
        vector<int> f(n, 1);
        auto g = f;

        // 填表
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], g[j] + 1);
                } else if (nums[j] > nums[i]) {
                    g[i] = max(g[i], f[j] + 1);
                }
            }
        }

        return max(*max_element(f.begin(), f.end()),
                   *max_element(g.begin(), g.end()));
    }
};

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

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

相关文章

720漫游工具又双叒叕上新了一批新功能

一、720漫游全景图片上传支持「自定义水印」 全景图片素材上传支持自定义水印设置&#xff0c;通过自定义水印&#xff0c;可以在全景图片上打上自定义的水印图片保护用户版权利益&#xff0c;同时强化自身品牌露出。具体操作如下&#xff1a; 打开「创建720漫游作品页」-选择…

MIL图像处理那些事:定义感兴趣区域ROI的两种方法(示例项目C#源码)

文章目录 效果展示第一种方法:通过鼠标框选GetROIForm构造函数如何缩放--MdispZoom的使用Ctr+滚轮缩放放大两倍:如何平移--MdispPan的使用双击返回ROI第二种方法:直接编辑ROI框显示ROI示例项目C#源码(百度网盘)本示例提供两种方法定义感兴趣区域ROI 效果展示 第一种方法:通过鼠…

从广州到上海|荣载光的智慧 与SSHT共同探索智能照明更多想象空间

随着生活水平的提高&#xff0c;大众对高品质生活的追求脚步逐步加快&#xff0c;人们对智能照明的需求日益多样化&#xff0c;不再仅仅满足于传统的照明功能&#xff0c;而是转向智能照明系统&#xff0c;提出更高的需求。 展望未来&#xff0c;中国智能照明市场预计将迎来全…

定时触发-uniapp + uniCloud 订阅消息实战教程(三)

上一节已经对云函数有了一定的了解&#xff0c;但是&#xff0c;为了发送订阅消息&#xff0c;只会云函数还是差了那么一点意思&#xff0c;所以接下来的这一节&#xff0c;将带领大家熟悉一下定时触发。 熟悉定时触发 如果云函数需要定时/定期执行&#xff0c;即定时触发&…

云计算【第一阶段(19)】磁盘管理与文件系统 LVM与磁盘配额(二)

目录 一、LVM概述 1.1、LVM机制的基本概念 ​编辑 1.2、LVM的管理命令 1.3、lvm存储 两种机制 1.4、lvm应用实例 二、磁盘配额概述 2.1、设置磁盘配额 2.2.1、实现磁盘限额的条件 2.2.2、linux磁盘限额的特点 2.2.3、磁盘配额管理 一、LVM概述 1.1、LVM机制的基本概…

一会一展一赛,共绘 AI 新篇章!和鲸出席 GAITC 2024 全球人工智能技术大会

“毕竟西湖六月中&#xff0c;风光不与四时同。” ——宋 杨万里 6 月 22 日&#xff0c;由中国人工智能学会主办的 2024 全球人工智能技术大会 (GAITC 2024) 于杭州市余杭区未来科技城璀璨启幕&#xff0c;上海和今信息科技有限公司&#xff08;以下简称“和鲸科技”&#x…

《知人寻香—2024香水香氛趋势白皮书》

本报告由小红书联合凯度中国共同发布:《知人寻香—2024香水香氛趋势白皮书》。这份报告细致描绘了中国香水市场的五大消费人群特征和六大消费趋势,为香水品牌提供了丰富的创新灵感。它不仅分析了中国香水市场目前的发展趋势,还预测了未来市场的潜在增长,以及消费者对香水香氛产…

主变变压器保护屏组成,功能介绍

主变变压器保护屏组成&#xff0c;功能介绍 在电力系统中&#xff0c;主变变压器是核心设备之一&#xff0c;对于保障电力系统的稳定运行起着至关重要的作用。为了确保主变变压器的正常运行&#xff0c;需要采用各种保护措施。其中&#xff0c;主变变压器保护屏是其中的重要组成…

Redis-哨兵模式-主机宕机-推选新主机的过程

文章目录 1、为哨兵模式准备配置文件2、启动哨兵3、主机6379宕机3.4、查看sentinel控制台日志3.5、查看6380主从信息 4、复活63794.1、再次查看sentinel控制台日志 1、为哨兵模式准备配置文件 [rootlocalhost redis]# ll 总用量 244 drwxr-xr-x. 2 root root 150 12月 6 2…

电脑录屏快捷键是哪个?电脑录屏,3个快捷键教会你

“怎样才能快速进行电脑录屏&#xff1f;找了好久的电脑录屏快捷键也没有找到&#xff0c;如果录屏要进行一系列的操作&#xff0c;那精彩内容早就错过了&#xff0c;想问问大家有没有录屏的快捷键方法可以分享一下&#xff1f;” 在我们的日常生活和工作中&#xff0c;电脑录…

服务器(Linux系统的使用)——自学习梳理

root表示用户名 后是机器的名字 ~表示文件夹&#xff0c;刚上来是默认的用户目录 ls -a 可以显示出隐藏的文件 蓝色的表示文件夹 白色的是文件 ll -a 查看详细信息 total表示所占磁盘总大小 一般以KB为单位 d开头表示文件夹 -代表文件 后面得三组rwx分别对应管理员用户-组…

期末考试结束后,老师怎样一对一发布成绩?

期末的"大考"终于落下帷幕。老师们&#xff0c;你们是不是也在想&#xff0c;怎样才能既高效又私密地把成绩告诉给每一位学生和家长呢&#xff1f;别急&#xff0c;我来给各位支个招。 一、保护隐私&#xff0c;一对一传递 想象一下&#xff0c;如果成绩和评语能够像…

ANSYS动力电池仿真应用案例

由于电池研究过程中的物理现象具有相差非常大的时间和空间维度&#xff0c;ANSYS为此提供了MSMD的解决方法&#xff1b;还针对电池使用过程中可能遇到的问题&#xff0c;如短路、热失控等提供了相应的模型和解决方案。 目录 1 电池行业发展趋势 2 燃料电池定义和分类 3 燃料…

华为eNSP模拟器下载地址

一、依赖程序 VirtualBox&#xff1a;https://cloud.rsecc.cn/softlink/VirtualBox-5.2.26-128414-Win.exe WinPcap&#xff1a;https://cloud.rsecc.cn/softlink/WinPcap_4_1_3.exe Wireshark&#xff1a;https://cloud.rsecc.cn/softlink/Wireshark-win64-3.0.6.exe 需要…

Mac系统Testim使用说明

1.Testim简介 Testim是一款基于AI的自动化测试工具&#xff0c;可以快速编写稳定的测试和 TestOps 工具&#xff0c;以帮助团队有效地扩展测试。 2. 注册账户&#xff08;要使用企业账号&#xff09; 官网地址&#xff1a;https://www.testim.io/&#xff0c;登录成功后主页…

nvm下载node慢或失败解决方案

打开nvm目录&#xff0c;找到setting.txt 文件夹打开粘贴进去如下路径node_mirror: https://npmmirror.com/mirrors/node/ npm_mirror: https://npmmirror.com/mirrors/npm/保存即可

鸣潮基于虚幻引擎4的多平台效果和性能优化实践

《鸣潮》基于虚幻引擎4的多平台效果和性能优化实践 | 王宏波 库洛游戏 文章目录 《鸣潮》基于虚幻引擎4的多平台效果和性能优化实践 | 王宏波 库洛游戏Why Deferred Shading移动端高质量的TAAU渲染流程Ghost和Flicker优化&#xff0c;一些图像空间算法的融入动静态像素的差异处…

在华为服务器上编译C++工程的若干错误以及排查方法和解决方法记录

目录 1 报错 2 查找错误原因 2.1 方法一&#xff1a;ldd命令 2.2 方法二&#xff1a;警告信息里面 3 解决错误 3.1 libpng16.so.16 和 libbrotlidec.so.1 问题 3.2 libdevmmap.so 和 libslog.so库问题 3.3 剩余错误 3.3.1 libacllite.so错误解决 3.3.2 libtaclstream…

怎么在大模型之上构建应用?构建人工智能上层应用的框架——langchain

“langchain&#xff0c;在大模型之上构建应用的脚手架” 在大模型之上构建应用需要很多的步骤&#xff0c;比如文档加载&#xff0c;数据库读取&#xff0c;大模型加载&#xff0c;以及各个环节的连接等。 因此&#xff0c;就有了langchain这个开发框架&#xff0c;它的功能…

CI部署流程简图

&#x1f31f;&#x1f30c; 欢迎来到知识与创意的殿堂 — 远见阁小民的世界&#xff01;&#x1f680; &#x1f31f;&#x1f9ed; 在这里&#xff0c;我们一起探索技术的奥秘&#xff0c;一起在知识的海洋中遨游。 &#x1f31f;&#x1f9ed; 在这里&#xff0c;每个错误都…