`
xinjiang
  • 浏览: 55590 次
  • 性别: 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}, ...

    最长上升子序列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 数组后,其中的最大值就是最长上升子序列的长

    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的不下降序列。程序...

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

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

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

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

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

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

    最长上升子序列.docx

    - 在完成上述步骤后,`dp`数组中的最大值即为整个数组的最长上升子序列的长度。 #### 四、Python代码示例 以下是一个用Python实现的LIS问题的动态规划解法示例: ```python def length_of_lis(nums): if not ...

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

    首先,初始化数组f,表示每个位置的最长上升子序列长度,初始所有值为1。然后,遍历序列,对于每个元素i,再次遍历之前的元素j,如果j小于i且a[j]小于a[i],并且f[j]+1大于f[i],则更新f[i]为f[j]+1。最后,找出f...

    最长上升子序列(信息学奥赛一本通-T1281).rar

    3. 最后,dp数组中的最大值即为最长上升子序列的长度。 除了动态规划,还可以使用二分查找来优化解决方案。这种方法称为二分查找法+单调队列。维护一个单调递减的队列,每次在队列中插入新元素时,如果新元素小于...

    最长递减子设有一个整数序列A1, A2, ... An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 252 245 250 其中最长序列为: 300 275 200 138 所以M=4, N=3

    An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 252 245 250 其中最长序列为: 300 275 200 138 ...

    Java实现 LeetCode 300 最长上升子序列

    给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的组合,你只需要...

    javascript-leetcode面试题解动态规划问题之第300题最长上升子序列-题解.zip

    3. 最后dp数组中的最大值即为最长上升子序列的长度。 在JavaScript中实现这个算法,可以使用以下代码示例: ```javascript function lengthOfLIS(nums) { if (nums.length === 0) return 0; let dp = new ...

    最长公共子序列,分治法,算法C++

    初始化时,`c[0][0]`设置为0,因为没有元素的公共子序列长度为0。同时,边界条件`c[i][0]`和`c[0][j]`都设为0,表示只有一个序列时,LCS的长度自然为0。 接下来的双层循环是核心部分,用于计算每个`c[i][j]`的值。...

    js代码-16.4 最长上升子序列

    - 如果`dp[i] [j] + 1`,则更新`dp[i] = dp[j] + 1`,表示以`nums[i]`为结尾的最长上升子序列长度更新为`dp[j] + 1`。 3. 在遍历结束后,`dp`数组中的最大值即为最长上升子序列的长度。 在JavaScript中,代码可能...

    DP、二分-LeetCode300. 最长上升子序列(Python)

    在LeetCode的第300题“最长上升子序列”中,目标是找出给定无序整数数组中的最长上升子序列(Longest Increasing Subsequence, LIS)的长度。上升子序列是指序列中的元素逐个严格递增,但不一定是连续的。例如,对于...

    最长不下降子序列

    要注意的是,`D[]` 数组在算法结束时并不直接给出最长上升子序列,而是记录了长度为 `k` 的最长上升子序列的最小末尾元素。为了获得实际的子序列,我们需要回溯数组 `D[]` 和原始序列 `A[]`。 总的来说,解决最长不...

    c语言最长上升子集.rar

    最长上升子序列问题可以这样定义:给定一个无序的整数数组,任务是找到该数组中一个最长的子序列,使得这个子序列中的元素从左到右是严格递增的...最后,我们遍历dp数组,找到其中的最大值,即为最长上升子序列的长度。

Global site tag (gtag.js) - Google Analytics