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

交替序列长度的最大值

1、题目描述

给出n个正整数,你可以随意从中挑选一些数字组成 一段序列S,该序列满足以下两个条件:
1.奇偶交替排列:例如:"奇,偶,奇,偶,奇.…" 或者 "偶,奇,偶, 奇..."
2.前一个数必须严格小于下一数。
注意:挑选出来的数字可以任意排列组成S,不需要保持原本的相对顺序。
请你求出该序列S长度的最大值。

输入描述

输入的的第一行给出正整数n(1<= n<= 100)   代表数组的长度。
输入的第二行为n个正整数ai(1 <= ai<= 10^9),用空格分隔。


输出描述

输出序列S长度的最大值。

示例 1 

输入:

10
6 6 1 1 5 3 2 6 8 10
输出:

4


实例2
 

输入:

10
4 8 6 8 6 6 2 10 2 10

输出:

1

2、解题思路

要解决这个问题,我们需要找到满足特定条件的最长子序列。具体来说,序列中的数字必须严格递增且奇偶交替排列。我们可以通过动态规划的方法来高效地解决这个问题。

  1. 排序数组:首先将数组排序,这样我们可以方便地处理递增的条件。

  2. 动态规划:使用动态规划来记录以每个数字结尾的最长满足条件的子序列长度。我们需要维护两个动态规划数组:

    • dp_odd[i] 表示以第i个数字结尾且该数字为奇数时的最长子序列长度。

    • dp_even[i] 表示以第i个数字结尾且该数字为偶数时的最长子序列长度。

  3. 状态转移:对于每个数字,检查其奇偶性,并根据前一个数字的奇偶性来更新当前数字的动态规划值。具体来说:

    • 如果当前数字是奇数,它可以接在任意一个比它小的偶数后面,因此更新 dp_odd[i] 为 dp_even[j] + 1,其中 nums[j] < nums[i] 且 nums[j] 是偶数。

    • 同理,如果当前数字是偶数,它可以接在任意一个比它小的奇数后面,因此更新 dp_even[i] 为 dp_odd[j] + 1,其中 nums[j] < nums[i] 且 nums[j] 是奇数。

  4. 结果提取:最终结果是 dp_odd 和 dp_even 数组中的最大值。

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建Scanner对象用于读取输入Scanner scanner = new Scanner(System.in);// 读取数组的长度nint n = scanner.nextInt();// 创建数组nums用于存储输入的整数int[] nums = new int[n];// 读取n个整数并存入数组numsfor (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}// 对数组进行排序,以便后续处理递增条件Arrays.sort(nums);// 创建两个动态规划数组:// dpOdd[i]表示以nums[i]结尾且nums[i]为奇数的最长子序列长度// dpEven[i]表示以nums[i]结尾且nums[i]为偶数的最长子序列长度int[] dpOdd = new int[n];int[] dpEven = new int[n];// 初始化所有位置的最长子序列长度为1(至少包含自己)Arrays.fill(dpOdd, 1);Arrays.fill(dpEven, 1);// 用于记录最终结果,初始化为1(至少可以选一个数)int maxLen = 1;// 遍历数组中的每个数字for (int i = 0; i < n; i++) {// 检查当前数字是否为奇数if (nums[i] % 2 == 1) {// 如果是奇数,遍历前面的所有数字for (int j = 0; j < i; j++) {// 如果前面的数字是偶数且比当前数字小if (nums[j] < nums[i] && nums[j] % 2 == 0) {// 更新dpOdd[i]为dpEven[j]+1和当前值的较大者dpOdd[i] = Math.max(dpOdd[i], dpEven[j] + 1);}}// 更新全局最大值maxLen = Math.max(maxLen, dpOdd[i]);} else {// 如果是偶数,遍历前面的所有数字for (int j = 0; j < i; j++) {// 如果前面的数字是奇数且比当前数字小if (nums[j] < nums[i] && nums[j] % 2 == 1) {// 更新dpEven[i]为dpOdd[j]+1和当前值的较大者dpEven[i] = Math.max(dpEven[i], dpOdd[j] + 1);}}// 更新全局最大值maxLen = Math.max(maxLen, dpEven[i]);}}// 输出最长子序列的长度System.out.println(maxLen);}
}

代码解释

  1. 输入处理:读取输入的数组长度 n 和数组 nums

  2. 排序数组:将数组 nums 排序以便处理递增条件。

  3. 动态规划初始化:初始化两个动态规划数组 dpOdd 和 dpEven,分别记录以奇数和偶数结尾的最长子序列长度,初始值为1。

  4. 动态规划填充

    • 对于每个数字 nums[i],根据其奇偶性,检查所有比它小的数字 nums[j],并根据 nums[j] 的奇偶性更新 dpOdd[i] 或 dpEven[i]

  5. 结果提取:在填充动态规划数组的过程中,始终保持更新全局最大值 maxLen,最终输出该值。

相关文章:

交替序列长度的最大值

1、题目描述 给出n个正整数&#xff0c;你可以随意从中挑选一些数字组成 一段序列S&#xff0c;该序列满足以下两个条件&#xff1a; 1.奇偶交替排列&#xff1a;例如&#xff1a;"奇&#xff0c;偶&#xff0c;奇&#xff0c;偶&#xff0c;奇.…" 或者 "偶&a…...

追踪大型语言模型的思想(下)(来自针对Claude的分析)

多步推理 正如我们上面所讨论的&#xff0c;语言模型回答复杂问题的一种方式就是简单地记住答案。例如&#xff0c;如果问“达拉斯所在州的首府是哪里&#xff1f;”&#xff0c;一个“机械”的模型可以直接学会输出“奥斯汀”&#xff0c;而无需知道德克萨斯州&#xff0c;达拉…...

嵌入式通信协议总览篇:万物互联的基石

嵌入式系统的世界,是靠协议“说话”的世界。 在你设计一个智能设备、构建一个工业控制系统、开发一款 IoT 网关时,一个核心问题始终绕不开:**这些设备之间如何“对话”?**答案就是——通信协议。 本篇作为系列第一章,将带你全面理解嵌入式通信协议的全貌,为后续深入学习…...

Android 连接德佟打印机全实例+踩坑

文章目录 1. sdk下载2. 开始开发2.1 打印之前准备工作2.2 打印机是否连接检测2.3 打印框架设计 最近有个需求是要连接 德佟打印机 进行打印相关事宜, 现在就遇到的问题简单阐述一下。 1. sdk下载 我们首先需要在官网下载对应的SDK&#xff0c;地址为&#xff1a;https://www.d…...

TikTok 矩阵运营新手实操保姆级教程 2.0 版本

在当下这个全球化的数字浪潮中&#xff0c;TikTok 这片充满机遇的流量蓝海&#xff0c;正吸引着无数创业者和品牌方争相角逐。而要想在这激烈的竞争中脱颖而出&#xff0c;TikTok 矩阵运营无疑是至关重要的制胜法宝。今天&#xff0c;就给大家送上这份超实用的新手实操教程&…...

WordPress:Locoy.php火车头采集

<?php /* 模块参数列表&#xff1a; post_title 必选 标题 post_content 必选 内容 tag 可选 标签 post_category 可选 分类 post_date 可选 时间 post_excerpt 可选 摘要 post_author 可选 作者 category_description 可选 分类信息 post_cate_meta[name] 可选 自定义分…...

C++ 有哪些标准版本

目录 1.主要分为以下几个版本C98&#xff08;ISO/IEC 14882:1998&#xff09; 第一个国际标准C03&#xff08;ISO/IEC 14882:2003&#xff09;小幅度修订C11&#xff08;ISO/IEC 14882:2011&#xff09;一次重大更新C14&#xff08;ISO/IEC 14882:2014&#xff09;增量改进C17&…...

二、MySQL操作命令汇总

文章目录 二、MySQL操作命令汇总1.数据库操作2.表的增删改查2.1 查表2.2 建表给表添加注释假如表已经存在 2.3 删表2.4 查看表结构2.5 改表 3.简单查询3.1 查询单个字段3.2 查询多个字段3.3 查询所有字段3.4 查询结果去重3.5 查询结果排序3.6 查询结果限制条数3.7 查询分组结果…...

编程日志4.28

队列的链表表示代码 #include<iostream> #include<stdexcept> using namespace std; //队列 类的声明 template<typename T>//1.模板声明&#xff0c;表明Queue类是一个通用的模板类&#xff0c;可以用于存储任何类型的元素T class Queue {//2.Queue类的声…...

Qt 中信号与槽(signal-slot)机制支持 多种连接方式(ConnectionType)

Qt 中信号与槽&#xff08;signal-slot&#xff09;机制支持 多种连接方式&#xff08;ConnectionType&#xff09; Qt 中信号与槽&#xff08;signal-slot&#xff09;机制支持 多种连接方式&#xff08;ConnectionType&#xff09;&#xff0c;用于控制信号发出后如何调用槽…...

Python案例实战《手势识别》

目录 1、效果图2、手势识别关键步骤&#xff08;1&#xff09; 导入必要的库&#xff08;2&#xff09;配置 MediaPipe&#xff08;3&#xff09;启动摄像头&#xff08;4&#xff09;设置手指张开判断的距离阈值&#xff08;5&#xff09;计算手指之间的欧几里得距离&#xff…...

NGINX `ngx_http_charset_module` 字符集声明与编码转换

一、模块定位与功能 ngx_http_charset_module 主要提供两大能力&#xff1a; 响应头声明&#xff1a;在 Content-Type 头部自动添加 ; charsetXXX&#xff0c;告知客户端所用字符集。单向编码转换&#xff1a;在 NGINX 层将一种单字节编码&#xff08;如 koi8-r、windows-125…...

进程与线程详细介绍

目录 一 进程概念 二 进程的组成 2.1 PCB 2.2 数据段 2.3 程序段 三 进程的五大特点 四 进程的创建与销毁 五 线程概念 六 线程特征 七 进程与线程的区别与联系 区别 联系 一 进程概念 进程是程序的一次执行过程&#xff0c;是操作系统进行资源分配和调度的基本单位…...

JAVA中ArrayList的解析

gogogo出发喽&#xff01;让我们来认识一下它吧 什么是ArrayList Java 中的 ArrayList 是 Java 集合框架中的重要类&#xff0c;用于实现动态数组 动态数组&#xff1a;可按需自动扩展或缩小&#xff0c;无需手动管理数组大小。比如不断向 ArrayList 添加元素时&#xff0c;…...

【LLM+Code】Devin PromptTools详细解读

Devin 官网&#xff1a;https://devin.ai/ Prompt 大部分篇幅都是tools的直出的description和parameters的一些信息 其他的包含 Communicatework的一些指导Best PracticesInformation HandlingData SecurityResponse Limitationsplanthink You are Devin, a software engi…...

AI应用开发实战分享

一、前言 30年前的IntelWindows互相绑定&#xff0c;让世界被计算机技术重构了一次&#xff0c;有了程序员这个工种。十几年前iPhone、Android前后脚发布&#xff0c;智能手机和移动App互相绑定&#xff0c;引爆了一个长达十几年的移动互联网大跃进时代。而随着人工智能大模型…...

浅聊find_package命令的搜索模式(Search Modes)

背景 find_package应该算是我们使用最多的cmake命令了。但是它是如何找到上游库的.cmake文件的&#xff1f; 根据官方文档&#xff0c;整理下find_package涉及到的搜索模式。 搜索模式 find_package涉及到的搜索模式有两种&#xff1a;模块模式(Module mode)和配置模式(Conf…...

FPGA图像处理(二)-----彩色图像灰度化

由于fpga实现除法相对复杂&#xff0c;故将除法变为乘法再移位。因此每种方法对图像输入数据均分3步进行&#xff0c;极其有效信号打三拍处理。 timescale 1ns / 1ps // // Description: 彩色图像灰度化 // module image_rgb2gray(input wire clk ,input wir…...

Ultralytics中的YOLODataset和BaseDataset

YOLODataset 和 BaseDataset 是 Ultralytics YOLO 框架中用于加载和处理数据集的两个关键类。 YOLODataset类&#xff08;ultralytics/data/dataset.py&#xff09;继承于 BaseDataset类&#xff08;ultralytics/data/base.py&#xff09; BaseDataset() BaseDataset 是一个…...

Mac 使用 Charles代理生成https服务

在Mac电脑上使用Charles软件通过代理生成HTTPS服务&#xff0c;让手机访问电脑的开发地址&#xff0c;可按以下步骤操作&#xff1a; 一、Charles软件设置 安装与启动Charles&#xff1a;从Charles官网下载并安装Charles软件&#xff0c;之后启动它。开启代理服务 点击菜单栏…...

【PostgreSQL】数据库主从库备份与高可用部署

文章目录 一、架构设计原理二、部署清单示例2.1 StatefulSet配置片段2.2 Service配置三、配置详解3.1 主节点postgresql.conf3.2 从节点配置四、初始化流程4.1 创建复制用户4.2 配置pg_hba.conf五、故障转移示例5.1 自动切换脚本5.2 手动提升从节点六、监控与维护6.1 关键监控指…...

ERP进销存系统源码,SaaS模式多租户ERP管理系统,SpringBoot、Vue、UniAPP技术框架

SaaS ERP管理系统源码&#xff0c;覆盖了整个生产企业所有部门的管理&#xff1a;采购、销售、仓库、生产、财务、质量、OA&#xff1a; ERP源码技术架构&#xff1a;SpringBootVueElementUIUniAPP ERP系统功能清单&#xff1a; 流程处理中心&#xff1a;待审批任务、已审批任…...

Decode rpc invocation failed: null -> DecodeableRpcInvocation

DecodeableRpcInvocation 异常情况解决方法 错误警告官方FAQ 异常情况 记录一下Dubbo调用异常 java.util.concurrent.ExecutionException: org.apache.dubbo.remoting.TimeoutException: Waiting server-side response timeout by scan timer. start time: 2025-05-07 22:09:5…...

VAE和Stable Diffusion的关系

文章目录 ✅ 简单回顾&#xff1a;什么是 VAE&#xff1f;&#x1f504; Stable Diffusion 和 VAE 的关系&#xff1a;&#x1f3af; 编码器&#xff1a;&#x1f4a5; 解码器&#xff1a; &#x1f914; 那 Stable Diffusion 本身是 VAE 吗&#xff1f;&#x1f9e0; 简要对比…...

stable Diffusion模型结构

详细描述一下stable Diffusion的推理过程 其实很简单 prompt先经过textencoder tokenizer&#xff0c;embedding 随机生成噪声图片 通过vae encode压缩成潜空间大小 unet with cross attn 去噪 并融合文本信息 # 上面两个信息如何混合 cross-attention sd模型中各种不同的采样器…...

Milvus(16):索引解释

索引是建立在数据之上的附加结构。其内部结构取决于所使用的近似近邻搜索算法。索引可以加快搜索速度&#xff0c;但在搜索过程中会产生额外的预处理时间、空间和 RAM。此外&#xff0c;使用索引通常会降低召回率&#xff08;虽然影响可以忽略不计&#xff0c;但仍然很重要&…...

数字化转型-4A架构之应用架构

系列文章 数字化转型-4A架构&#xff08;业务架构、应用架构、数据架构、技术架构&#xff09;数字化转型-4A架构之业务架构 前言 应用架构AA&#xff08;Application Architecture&#xff09;是规划支撑业务的核心系统与功能模块&#xff0c;实现端到端协同。 一、什么是应…...

中间件-RocketMQ

RocketMQ 基本架构消息模型消费者消费消息模式顺序消息机制延迟消息批量消息事务消息消息重试最佳实践 基本架构 nameServer: 维护broker列表信息&#xff0c;客户端连接时只需要连接nameServer。可配置成集群。 broker&#xff1a;broker分为master和slave&#xff0c;master负…...

AI开发playwright tool提示词

[TASK] 生成一个isModuleElementObject function&#xff0c;若element的qa-test class在对象moduleObj {"qa-test-mycourses-course": "qa-test-mycourses-course-title", "qa-test-discussion-module": "qa-test-discussion-description&…...

《Origin画百图》之带显著性标记的多因子分组柱状图

带显著性标记的多因子分组柱状图 需要数据&#xff1a; 组1&#xff08;大类&#xff09; 组2&#xff08;小类&#xff09; Y数据 Y误差 选中Y数据和Y误差两列数据&#xff0c; 点击绘图--分组图--多因子分组柱状图 数据列就是上一步选择的Y和Y误差&#xff0c; 点击子组…...

邮件发送频率如何设置?尊重文化差异是关键!

一、不同文化背景&#xff0c;邮件频率大不同 1.工作习惯不一样 一些西方国家&#xff0c;美国和欧洲工作时间和个人时间分得很清楚。工作日的上午 9 点到下午 5 点&#xff0c;这期间发邮件&#xff0c;收件人大概率会看也会回。但是在深夜或者周末发邮件容易让收件人觉得你…...

Python 识别图片上标点位置

Python识别图片上标点位置 要识别图片上的标点位置&#xff0c;可以使用Python中的OpenCV库。以下是几种常见的方法&#xff1a; 方法一&#xff1a;使用颜色阈值识别 import cv2 import numpy as np# 读取图片 image cv2.imread(image.jpg)# 转换为HSV颜色空间 hsv cv2.c…...

JDK Version Manager (JVMS)

以下是使用 JDK Version Manager (JVMS) 工具在Windows系统中安装JDK的详细步骤及注意事项&#xff0c;结合多篇搜索结果整理而成&#xff1a; --- 一、安装前准备 1. 下载JVMS - 访问 [GitHub Releases页面](https://github.com/ystyle/jvms/releases) 或镜像地址&#x…...

办公学习 效率提升 超级PDF处理软件 转换批量 本地处理

各位办公小能手们&#xff01;我跟你们说啊&#xff0c;有个软件叫超级PDF&#xff0c;那可真是PDF文件处理界的全能选手&#xff0c;专门解决咱们办公、学习时文档管理的各种难题。接下来我给大家好好唠唠它的厉害之处。 先说说它的核心功能。第一是格式转换&#xff0c;这软件…...

阿里云服务器-centos部署定时同步数据库数据-dbswitch

前言&#xff1a; 本文章介绍通过dbswitch工具实现2个mysql数据库之间实现自动同步数据。 应用场景&#xff1a;公司要求实现正式环境数据库数据自动冷备 dbswitch依赖环境&#xff1a;git ,maven,jdk 方式一&#xff1a; 不需要在服务器中安装git和maven&#xff0c;直接用…...

C++函数栈帧详解

函数栈帧的创建和销毁 在不同的编译器下&#xff0c;函数调用过程中栈帧的创建是略有差异的&#xff0c;具体取决于编译器的实现&#xff01; 且需要注意的是&#xff0c;越高级的编译器越不容易观察到函数栈帧的内部的实现&#xff1b; 关于函数栈帧的维护这里我们要重点介…...

Wireshark抓账号密码

训练内容&#xff1a; 1. 安装Ethereal或者Wireshark&#xff0c;熟悉网络嗅探器的使用方法&#xff1b; 2. 实现浏览器与IIS服务器的ssl安全访问&#xff1b; 3. 利用网络嗅探器截获浏览器访问IIS服务器之间数据包&#xff0c;包括有ssl安全连接&#xff08;https方式&am…...

【hot100】bug指南记录1

之前学了一阵C&#xff0c;还是更熟悉C的语法呀&#xff0c;转Java还有点不适应........ 这个系列纯纯记录自己刷题犯的愚蠢的错误......hhhh&#xff0c;我是人&#xff0c;one 愚蠢的码人...... 巩固巩固基础好吗&#xff1f;&#xff01;编程菜鸟.......hhh&#xff0c;又…...

物联网从HomeAssistant开始

文章目录 一、在树梅派5上安装home-assistant二、接入米家1.对比下趋势2.手动安装插件3.配置方式 三、接入公牛1.手动安装插件2.配置方式 一、在树梅派5上安装home-assistant https://www.home-assistant.io/installation/ https://github.com/home-assistant/operating-syste…...

2025年渗透测试面试题总结-网络安全、Web安全、渗透测试笔试总结(一)(附回答)(题目+回答)

网络安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 网络安全、Web安全、渗透测试笔试总结(一) 1.什么是 WebShell? 2.什么是网络钓鱼&#xff1f; 3.你获取网络…...

C++ set和map系列(关联式容器)的介绍及使用

欢迎来到干货小仓库 "一个好汉三个帮&#xff0c;程序员同样如此" 1.关联式容器 STL中的容器分为两类&#xff0c;序列式容器和关联式容器。 序列式容器&#xff1a;例如STL库中的vector、list和deque、forward_list(C11)等&#xff0c;这些容器统称为序列式容器&…...

C#与Halcon联合编程

一、加载图片 导入并初始化 using HalconDotNet; ho_Image new HObject();需要在引用中导入 halcondotnet.dll 关联句柄 打开新窗口 //创建一个句柄变量 绑定winform 窗口 HTuple winfowFater this.pictureBox1.Handle; //打开新的窗口 HOperatorSet.SetWindowAttr(&qu…...

5.0.4 VisualStateManager(视觉状态管理器)使用说明

在 WPF 中,VisualStateManager(视觉状态管理器)是用于管理控件在不同状态下的外观变化的核心组件。它通过定义视觉状态(如按钮的默认、悬停、按下状态)和状态过渡动画,使控件在不同交互场景下动态切换样式,而无需重写整个控件模板。以下是其核心用法和示例: 1. 基本概…...

onenet连接微信小程序(mqtt协议)

一、关于mqtt协议 mqtt协议常用于物联网&#xff0c;是一种轻量级的消息推送协议。 其中有三个角色&#xff0c;Publisher设备&#xff08;客户端&#xff09;发布主题到服务器&#xff0c;其他的设备通过订阅主题&#xff0c;获取该主题下的消息&#xff0c;Publisher可以发…...

IT需求规格说明书,IT软件系统需求设计文档(DOC)

1 范围 1.1 系统概述 1.2 文档概述 1.3 术语及缩略语 2 引用文档 3 需求 3.1 要求的状态和方式 3.2 系统能力需求 3.3 系统外部接口需求 3.3.1 管理接口 3.3.2 业务接口 3.4 系统内部接口需求 3.5 系统内部数据需求 3.6 适应性需求 3.7 安全性需求 3.8 保密性需…...

探索 DevExpress:构建卓越应用的得力助手

探索 DevExpress&#xff1a;构建卓越应用的得力助手 在当今竞争激烈的软件开发领域&#xff0c;打造高效、美观且功能强大的应用程序是每个开发者的追求。而 DevExpress 作为一款备受瞩目的开发工具&#xff0c;为开发者们提供了实现这一目标的有力支持。在本专栏博客中&…...

康养休闲旅游住宿服务实训室:构建产教融合新标杆

随着健康中国战略的深入实施与银发经济市场的持续扩张&#xff0c;康养休闲旅游作为融合健康管理、文化体验与休闲度假的复合型产业&#xff0c;正迎来前所未有的发展机遇。北京凯禾瑞华科技有限公司依托其在智慧康养领域的技术积淀与产业洞察&#xff0c;创新推出“康养休闲旅…...

Python 程序设计教程:构建您的第一个计算器类

Python 程序设计教程:构建您的第一个计算器类 1. 引言:为什么要学习类? 面向对象编程 (Object-Oriented Programming, OOP) 是一种强大的编程范式,它通过将数据和操作数据的函数(方法)捆绑在一起来组织和结构化代码 1。类 (Class) 是 OOP 的核心概念,不仅在 Python 中…...

深入浅出理解常见的分布式ID解决方案

分布式ID在构建大规模分布式系统时扮演着至关重要的角色&#xff0c;主要用于确保在分布式环境中数据的唯一性和一致性。以下是分布式ID的几个主要作用&#xff1a; 确保唯一性&#xff1a;在分布式系统中&#xff0c;可能有成千上万个实例同时请求ID。分布式ID生成系统能保证即…...

mac 使用 Docker 安装向量数据库Milvus独立版的保姆级别教程

Milvus 特点&#xff1a;开源的云原生向量数据库&#xff0c;支持多种索引类型和GPU加速&#xff0c;能够在亿级向量规模下实现低延迟高吞吐。具有灵活的部署选项和强大的社区支持。 适用场景&#xff1a;适合处理超大规模数据和高性能需求的应用&#xff0c;如图像搜索、推荐…...