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

动态规划专题5:最长上升子序列

描述

给定一个长度为 N 的整数序列 A

找到一组最长的整数序列 x 满足:

1    <=    x1    <    x2    <    ...    <    xk    <=    N

A[x1] < A[x2]  <    ...     <   A[xk]

即寻找 A 的一个最长子序列,满足:

该子序列中每个元素递增

输入描述

第一行一个整数N(N<=1000) 表示长度,第二行 N个数 A[i]表示序列里面的数,每个数不超过int范围。

输出描述

一行 表示最长递增子序列的长度

用例输入 1 

6
1 6 2 5 4 7

用例输出 1 

4

例1中,最长上升子序列为:

1 6 2 5 4

1 6 2 5 4 7。

利用线性动态规划。

#include <bits/stdc++.h>
using namespace std;
int s[1010],dp[1010],mx,n;
int main(){cin>>n;if(n==1){//特判cout<<1;return 0;}for(int i=1;i<=n;i++){//每个格子都是一个上升子序列cin>>s[i];dp[i]=1;}for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(s[i]>s[j]){dp[i]=max(dp[i],dp[j]+1);mx=max(mx,dp[i]);//只要前面格子的值比它小,他与前面那个格子所组成的上升子序列即为前一个格子所组成的上升子序列加上当前的格子}}}cout<<mx;return 0;
}

http://www.xdnf.cn/news/4483.html

相关文章:

  • LeetCode hot 100—括号生成
  • 数据中台(大数据平台)之数据质量管理
  • 3.Rust + Axum 提取器模式深度剖析
  • 【Python Cookbook】迭代器与生成器(一)
  • 【Qt】初识Qt(一)
  • Oracle 12.1.0.2补丁安装全流程
  • FPGA阵列
  • ZStack文档DevOps平台建设实践
  • 设计模式每日硬核训练 Day 14:组合模式(Composite Pattern)完整讲解与实战应用
  • 基于Django实现的图书分析大屏系统项目
  • Linux 常用命令总结
  • NLP高频面试题(四十六)——Transformer 架构中的位置编码及其演化详解
  • MCP和A2A是什么?
  • FreeRTOS事件标志组
  • 【Linux】第八章 监控和管理Linux进程
  • 关于Diamond机械手的运动学与动力学的推导
  • 【力扣刷题】49字母异位词分组,不用哈希,c语言实现
  • 《AI大模型应知应会100篇》第22篇:系统提示词(System Prompt)设计与优化
  • 基础知识 - 结构体
  • 首席人工智能官(Chief Artificial Intelligence Officer,CAIO)的详细解析
  • 从“链主”到“全链”:供应链数字化转型的底层逻辑
  • 智能sc一面
  • 【cocos creator 3.x】cocos creator2.x项目升级3.x项目改动点
  • 士兵乱斗(贪心)
  • 前端api(请求后端)简易template
  • Python高级爬虫之JS逆向+安卓逆向1.5节: 控制结构
  • docker harbor私有仓库登录报错
  • Ubuntu利用docker搭建Java相关环境问题记录
  • 如何有效防止服务器被攻击
  • 在激烈竞争下B端HMI设计怎样打造独特用户体验?