`
xinjiang
  • 浏览: 56123 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求最长上升子序列的最大长度

J# 
阅读更多

问题描述

一个数的序列 bi,当 b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一

个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里 1 <= i1 < i2 < ... <

iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。

这些子序列中最长的长度是 4,比如子序列(1, 3, 5, 8).

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

输入数据

输入的第一行是序列的长度 N (1 <= N <= 1000)。第二行给出序列中的 N个整数,这些

整数的取值范围都在 0到 10000。

输出要求

最长上升子序列的长度。

输入样例

7

1 7 3 5 9 4 8

输出样例

4

#include <stdio.h>
#include <string.h>
int arry[1001];
int len[1001];

int main()
{
    int i, j;
    int n, maxLen;
    scanf("%d", &n);
    for( i = 1; i <= n; i++ )
    {
       scanf("%d", &arry[i]);
    }
    len[1] = 1;
    for( i = 2; i <= n; i++ )
    {
       maxLen = 0;
       for( j = 1; j < i; j++ )
       {
          if( len[j] > maxLen && arry[j] < arry[i] )
          {
              /*
              *如果i位置的权值大于j位置的权值,
              *且j处得长度大于j以前的长度,i才能加入到j的后面
              */
             maxLen = len[j];
          }
       }
       len[i] = maxLen+1;
    }

    maxLen = 0;
    for( i = 1; i <= n; i++ )
    {
       if( len[i] > maxLen )  maxLen = len[i];
    }
    printf("%d\n", maxLen);
    return 0;
}
 
分享到:
评论

相关推荐

    求出最长上升子序列中各个元素

    最长上升子序列是指在一个给定的序列中,找到一个子序列,要求这个子序列中的元素是严格递增的,并且它的长度最大。例如,在序列`[10, 9, 2, 5, 3, 7, 101, 18]`中,最长上升子序列有`[2, 3, 7, 101]`和`[10, 2, 5, ...

    8596 最长上升子序列

    ### 8596 最长上升子序列 #### 问题描述 给定一个整数序列 \(a_1, a_2, \ldots, a_N\),其中 \(1 \leq N \leq 1000\),每个元素 \(a_i\) 的取值范围为 \(0\) 至 \(10000\)。定义一个序列 \(S = (a_{i_1}, a_{i_2}, ...

    最长上升子序列最长上升子序列PDF

    最终,我们需要找到dp数组中的最大值,这个最大值就是整个序列的最长上升子序列的长度。 除了直接使用动态规划外,还有一种优化的方法,即通过二分查找加动态规划来降低算法的时间复杂度。在这种优化方法中,我们用...

    最长上升子序列nlgn源码

    输入序列,求最长上升子序列的长度,算法复杂度nlgn

    最长上升子序列

    你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入字符串的处理 注意:这道题和其他题的输入输出不同,这题...

    什么是最长上升子序列,和最长不下降子序列有什么区别

    最长上升子序列(Longest Increasing Subsequence,简称 LIS)是一个经典的动态规划问题。给定一个无序的整数数组,找到其中最长上升子序列的长度。...结果:遍历完整个 dp 数组后,其中的最大值就是最长上升子序列的长

    leetcode-master-最长上升子序列

    然后取这些元素对应的最长上升子序列长度的最大值,加上当前元素,就是以它结尾的最长上升子序列的长度。 在实现上,通常会使用一个一维数组来存储中间结果,而不会真的去记录上升子序列本身,因为那样会大大增加...

    算法设计-最长上升子序列问题

    3. 遍历完成后,dp 数组中的最大值即为整个序列的最长上升子序列的长度。 为了优化算法的效率,还可以采取一些策略来减少计算量。例如,可以使用二分查找来加速确定当前元素的前驱位置,从而避免了线性查找的时间...

    大一下_算法提高课-最长上升子序列

    这个过程中,辅助数组的最大长度就是当前的最长上升子序列的长度。 在实际应用中,最长上升子序列问题不仅可以应用于序列分析,还可以用于解决实际问题,比如在生物信息学中分析DNA序列,在计算机视觉中用于图像...

    1281:最长上升子序列.7z

    1259:【例9.3】求最长不下降序列 【题目描述】 设有由n(1≤n≤200)个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j),若存在i1…且有b(i1)(i2)&lt;…(ie)则称为长度为e的不下降序列。程序...

    求解最长上升子序列的方法

    每个元素的最长上升子序列长度初始为1,即每个元素单独构成一个长度为1的上升子序列。接着,遍历数组,对于每个元素,通过比较它与之前所有元素的大小,来决定是否更新dp数组。如果发现某个更小的元素,则更新该位置...

    最长上升子序列(Longest Increasing Subsequence,LIS)动态规划解法的 Python 源码

    3. 遍历完所有的元素后,整个序列的最长上升子序列长度即为 dp 数组中的最大值。 使用 Python 实现 LSI 动态规划解法,关键代码可以分为以下几个部分: - 初始化一个长度为序列长度的 dp 数组,初始值设为 1(每个...

    最长上升子序列(Longest Increasing Subsequence,LIS)贪心 + 二分查找的 java 源码

    1. 初始化一个数组dp,用于存放当前找到的上升子序列,数组的第一个元素是数列的第一个元素,dp数组长度等于最长上升子序列的最大可能长度。 2. 遍历数列中的每个元素,对于每个元素: a. 使用二分查找,在dp数组中...

    C语言:基于c代码实现的最长上升子序列

    优化的关键在于,在更新最长上升子序列长度的同时,记录该长度所对应的序列的最后一个元素的位置。使用一个辅助数组来维护长度为`i`的上升子序列的最小末尾值,并对每个元素进行二分查找,这样可以得到一个时间...

    53、1281:最长上升子序列(A)+书画相关链接(十七)-2020.01.19.pdf

    - 第二段代码中同样使用动态规划,其中用f数组来保存每个位置的最长上升子序列长度,并在每次更新时寻找当前的最大值。 2. 动态规划(Dynamic Programming,简称DP): - 动态规划是一种算法思想,用于求解具有...

    最长公共上升子序列(LCIS)的平方算法

    3. **最长上升子序列 (LIS)**:对于一个序列S,其最长上升子序列是指S中的一个子序列,该子序列是严格递增的,且长度最长。 #### 三、问题定义 假设我们有两个字符串(或整数序列)a和b,我们的目标是找到这两个...

    对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度,这里的子序列定义为这样一个序列U1,U2...,其中Ui < Ui+1,且AUi < AUi+1

    在算法领域,最长上升子序列(Longest Increasing Subsequence,简称LIS)是一个经典问题,它涉及到找出一个给定序列中严格单调递增的子序列,并返回这个子序列的最大长度。LIS问题不仅是计算机科学中的一个基础问题...

Global site tag (gtag.js) - Google Analytics