力扣--动态规划1027.最长等差数列

思路分析:

  1. 使用动态规划的思想,定义二维数组dp,其中dp[i][j]表示以nums[i]为结尾,公差为(j-1000)的等差数列长度。为了适应负数的情况,将公差的范围设为[-1000, 1000],并且加上1000作为数组索引。

  2. 初始化result为0,用于存储最终的最长等差数列长度。

  3. 使用两层循环遍历数组,对于每一对(i, j),计算它们的差值diff = nums[j] - nums[i] + 1000

  4. 更新dp[j][diff]dp[i][diff] + 1,表示当前等差数列的长度比前一个等差数列长度多1。

  5. 在每次更新dp[j][diff]时,都更新一下result,取当前长度和之前的最大长度的较大值。

  6. 最终返回result作为结果,表示整个数组中最长的等差数列长度。

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        // 获取数组长度
        int n = nums.size();

        // 创建一个二维动态规划数组,dp[i][j]表示以nums[i]为结尾,公差为(j-1000)的等差数列长度
        // 为了适应负数的情况,将公差的范围设为[-1000, 1000],并且加上1000作为数组索引
        vector<vector<int>> dp(n, vector<int>(2002, 1));

        // 用于存储最终结果
        int result = 0;

        // 遍历数组,计算dp数组的值
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算当前等差数列的公差
                int diff = nums[j] - nums[i] + 1000;

                // 更新dp数组
                dp[j][diff] = dp[i][diff] + 1;

                // 更新最终结果
                result = max(result, dp[j][diff]);
            }
        }

        // 返回最终结果
        return result;
    }
};

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

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

相关文章

javaApI(Application Programming Interface)应用程序编程接口

ApI概念 Apl:指的是官方给开发人员提供的说明文档&#xff0c;对语言中有哪些类&#xff0c;类中有哪些方法进行说明 Objict 类 java.lang.Object 是java类体系结构中最顶层的类 Object可以表示java中任意的类 Object类中的方法 toString() 输出一个对象&#xff0c;但是…

Python服务器监测测试策略与工具:确保应用的高可用性!

在构建高可用性的应用程序时&#xff0c;服务器监测测试是至关重要的一环。Python作为一种强大的编程语言&#xff0c;提供了丰富的工具和库来帮助我们进行服务器监测测试。本文将介绍一些关键的策略和工具&#xff0c;帮助你确保应用的高可用性。 1. 监测策略的制定&#xff…

matlab|基于DistFlow潮流的配电网故障重构(输入任意线路)

目录 1 主要内容 2 部分代码 3 程序结果 4 下载链接 1 主要内容 程序采用适用于辐射状网络的DistFlow潮流模型&#xff0c;可输入任意故障线路编号&#xff0c;得到优化重构结果。这个程序是配电网故障重构可视化matlabyalmip的升级版&#xff0c;原来的程序是以电压质量作…

介绍 PIL+IPython.display+mtcnn for 音视频读取、标注

1. nn.NLLLoss是如何计算误差的? nn.NLLLoss是负对数似然损失函数&#xff0c;用于多分类问题中。它的计算方式如下&#xff1a;首先&#xff0c;对于每个样本&#xff0c;我们需要将其预测结果通过softmax函数转换为概率分布。softmax函数可以将一个向量映射为一个概率分布&…

第四套CCF信息学奥赛c++ CSP-J认证初级组 中小学信奥赛入门组初赛考前模拟冲刺题(阅读程序题)

第四套中小学信息学奥赛CSP-J考前冲刺题 二、阅读程序题 (程序输入不超过数组或字符串定义的范围&#xff0c;判断题正确填√错误填X;除特殊说明外&#xff0c;判断题 1.5分&#xff0c;选择题3分&#xff0c;共计40分) 第一题 归并排序 1 #include <iostream> 2 usi…

【Java程序设计】【C00285】基于Springboot的游戏分享网站(有论文)

基于Springboot的游戏分享网站&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的游戏分享网站 本系统分为系统功能模块、管理员功能模块以及用户功能模块。 系统功能模块&#xff1a;在网站首页可以查看首页、游戏…

Linux环境基础开发工具使用篇(三) git 与 gdb

一、版本控制器-git 1.简单理解: ①git既是服务端&#xff0c;又是客户端 ②git会记录版本的变化 ③git是一个去中心化的分布式软件 git/gitee 是基于git仓库搭建的网站&#xff0c;让版本管理可视化 2.git 三板斧提交代码 查看安装的git版本 git--version 命令行提交代…

SpringMVC 学习(四)之获取请求参数

目录 1 通过 HttpServletRequest 获取请求参数 2 通过控制器方法的形参获取请求参数 3 通过 POJO 获取请求参数&#xff08;重点&#xff09; 1 通过 HttpServletRequest 获取请求参数 public String handler1(HttpServletRequest request) <form action"${pageCont…

Linux 文件操作

目录 C语言下的文件操作 Linux下的文件操作 文件描述符的前因后果 文件描述符的概念 文件描述符的分配规则 理解C语言的FILE结构体 Linux重定向 文件缓冲区 文件系统 文件系统的概念 ext2文件系统 对ext2的补充 虚拟文件系统的概念 软硬链接 C语言下的文件操作 …

Java零基础 - 关键字 instanceof

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一个人虽可以走的更快&#xff0c;但一群人可以走的更远。 我是一名后…

【深入理解设计模式】代理设计模式

代理设计模式&#xff1a; 代理设计模式是一种结构型设计模式&#xff0c;它允许你提供一个替代物或占位符来控制对其他对象的访问。在代理模式中&#xff0c;一个类代表另一个类的功能。这种类型的设计模式属于结构型模式&#xff0c;因为该模式涉及类和对象的组合。 概述 …

外包干了3个月,技术倒退明显...

先说情况&#xff0c;大专毕业&#xff0c;18年通过校招进入湖南某软件公司&#xff0c;干了接近6年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试&#xf…

笔记本hp6930p安装Android-x86避坑日记

一、序言 农历癸卯年前大扫除&#xff0c;翻出老机hp6930p&#xff0c;闲来无事&#xff0c;便安装Android-x86玩玩&#xff0c;期间多次入坑&#xff0c;随手记之以避坑。 笔记本配置&#xff1a;T9600,4G内存&#xff0c;120G固态160G机械硬盘 二、Android-x86系统简介 官…

【QT+QGIS跨平台编译】之五十二:【QGIS_CORE跨平台编译】—【qgsexpressionlexer.cpp生成】

文章目录 一、Flex二、生成来源三、构建过程一、Flex Flex (fast lexical analyser generator) 是 Lex 的另一个替代品。它经常和自由软件 Bison 语法分析器生成器 一起使用。Flex 最初由 Vern Paxson 于 1987 年用 C 语言写成。 “flex 是一个生成扫描器的工具,能够识别文本中…

Vue + Echarts页面内存占用高问题解决

Vue Echarts页面内存占用高问题解决 1.问题描述 目前使用的是Vue2 Echarts4.x的组合&#xff0c;页面如下所示。 就是一个类似于神策的数据看板页面&#xff0c;左侧是一个导航栏&#xff0c;右侧看板页面中包含很多个报表图片&#xff0c;其中报表页面中对Echarts图表进…

前端工程化面试题 | 18.精选前端工程化高频面试题

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【AIGC大模型】跑通wonder3D (windows)

论文链接&#xff1a;https://arxiv.org/pdf/2310.15008.pdf windows10系统 显卡&#xff1a;NVIDIA rtx 2060 一、安装anaconda 二、安装CUDA 11.7 (CUDA Toolkit 11.7 Downloads | NVIDIA Developer) 和 cudnn 8.9.7(cuDNN Archive | NVIDIA Developer)库 CUDA选择自定…

人工智能 — 立体视觉、双目系统

目录 一、立体视觉1、定义2、应用领域3、原理 二、单目系统和双目系统1、单目系统2、双目系统 三、视差 一、立体视觉 1、定义 立体视觉是一种计算机视觉技术&#xff0c;其目的是从两幅或两幅以上的图像中推理出图像中每个像素点的深度信息。 2、应用领域 机器人、辅助驾驶…

《低功耗方法学》翻译——第十四章:电源切换网络设计

第十四章&#xff1a;电源切换网络设计 功率门控是在待机或休眠模式下降低漏电功率最有效的方法&#xff0c;但这种方法存在诸如休眠晶体管占用的硅面积、永久和虚拟电源网络的布线资源以及复杂的功率门控设计和实现过程等开销&#xff0c;影响设计风险和进度。 除了开销外&a…

万界星空科技商业开源MES

一、万界星空科技商业开源MES系统概述&#xff1a; 万界星空科技免费MES、开源MES、商业开源MES、市面上最好的开源MES、MES源代码、适合二开的开源MES。 1.万界星空开源MES制造执行系统的Java开源版本。 开源mes系统包括系统管理&#xff0c;车间基础数据管理&#xff0c;计…