最长上升子序列 POJ2533

简介:
Longest Ordered Subsequence
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 18853   Accepted: 8147

Description

A numeric sequence of  ai is ordered if  a1 <  a2 < ... <  aN. Let the subsequence of the given numeric sequence ( a1a2, ...,  aN) be any sequence ( ai1ai2, ...,  aiK), where 1 <=  i1 <  i2 < ... <  iK <=  N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

Source

Northeastern Europe 2002, Far-Eastern Subregion
 
题目的大意是:给出一序列,求出该序列的最长上升子序列的最大长度。
思路:用数组a[]存储序列,b[i]表示以a[i]为结尾的序列的最大长度。
因此要求出b[i]的最大值,即求出max{b[0],b[1]....b[i-1]}的最大值,那么b[i]的最大值为max{b[0],b[1]....b[i-1]}+1;
即可写出状态方程:b[i]=max{b[0],b[1].....b[j]}+1;(0<=j<i&&a[j]<a[i]),然后求出数组b[]中的最大值即为所求。
#include<iostream>
using  namespace  std;
 
int  main( void )
{
     int  i,j,n;
     int  a[1001];
     int  b[1001];
     int  max;
     scanf ( "%d" ,&n);
     for (i=0;i<n;i++)
     {
         scanf ( "%d" ,&a[i]);
         b[i]=1;
     }
     for (i=0;i<n;i++)
     {
         max=0;
         for (j=0;j<i;j++)
         {
             if (a[i]>a[j]&&b[j]>max)
             {
                 max=b[j];
             }
         }
         b[i]=max+1;
     }
     max=0;
     for (i=0;i<n;i++)
     {
         if (max<b[i])
             max=b[i];
     }
     printf ( "%d\n" ,max);
     return  0;
}
 
 
本文转载自海 子博客园博客,原文链接:http://www.cnblogs.com/dolphin0520/archive/2011/07/09/2102044.html 如需转载自行联系原作者
相关文章
wangEditor自动获取焦点
wangEditor自动获取焦点
427 0
|
8月前
|
弹性计算 自然语言处理 监控
深度测评OS Copilot
通过阿里云ECS控制台的Workbench远程连接登录服务器后,使用命令`sudo yum install -y os-copilot`安装OS Copilot。成功安装后,配置环境变量并用`rpm -q os-copilot`验证安装。使用`co 当前系统健康度`检查系统状态,加`-t`选项可直接进入agent模式,提升响应速度。创建任务文件并通过`co -f task -t`实现自动化批量处理,提高效率约30%。OS Copilot还提供自动化管理、简化命令行操作和日志分析等优势,适用于高效管理多个服务器实例的企业环境。
120 17
|
小程序 Java 程序员
扫盲:Java 后端开发常用的 10 种第三方服务(2)
扫盲:Java 后端开发常用的 10 种第三方服务
413 0
扫盲:Java 后端开发常用的 10 种第三方服务(2)
|
4天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1103 0
|
3天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
493 10
|
13天前
|
人工智能 运维 安全
|
12天前
|
人工智能 测试技术 API
智能体(AI Agent)搭建全攻略:从概念到实践的终极指南
在人工智能浪潮中,智能体(AI Agent)正成为变革性技术。它们具备自主决策、环境感知、任务执行等能力,广泛应用于日常任务与商业流程。本文详解智能体概念、架构及七步搭建指南,助你打造专属智能体,迎接智能自动化新时代。
|
4天前
|
弹性计算 Kubernetes jenkins
如何在 ECS/EKS 集群中有效使用 Jenkins
本文探讨了如何将 Jenkins 与 AWS ECS 和 EKS 集群集成,以构建高效、灵活且具备自动扩缩容能力的 CI/CD 流水线,提升软件交付效率并优化资源成本。
298 0
|
11天前
|
人工智能 异构计算
敬请锁定《C位面对面》,洞察通用计算如何在AI时代持续赋能企业创新,助力业务发展!
敬请锁定《C位面对面》,洞察通用计算如何在AI时代持续赋能企业创新,助力业务发展!
|
12天前
|
机器学习/深度学习 人工智能 自然语言处理
B站开源IndexTTS2,用极致表现力颠覆听觉体验
在语音合成技术不断演进的背景下,早期版本的IndexTTS虽然在多场景应用中展现出良好的表现,但在情感表达的细腻度与时长控制的精准性方面仍存在提升空间。为了解决这些问题,并进一步推动零样本语音合成在实际场景中的落地能力,B站语音团队对模型架构与训练策略进行了深度优化,推出了全新一代语音合成模型——IndexTTS2 。
802 23