问题描述
一个数的序列 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 最长上升子序列 #### 问题描述 给定一个整数序列 \(a_1, a_2, \ldots, a_N\),其中 \(1 \leq N \leq 1000\),每个元素 \(a_i\) 的取值范围为 \(0\) 至 \(10000\)。定义一个序列 \(S = (a_{i_1}, a_{i_2}, ...
输入序列,求最长上升子序列的长度,算法复杂度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 数组后,其中的最大值就是最长上升子序列的长
1259:【例9.3】求最长不下降序列 【题目描述】 设有由n(1≤n≤200)个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j),若存在i1…且有b(i1)(i2)<…(ie)则称为长度为e的不下降序列。程序...
优化的关键在于,在更新最长上升子序列长度的同时,记录该长度所对应的序列的最后一个元素的位置。使用一个辅助数组来维护长度为`i`的上升子序列的最小末尾值,并对每个元素进行二分查找,这样可以得到一个时间...
- 第二段代码中同样使用动态规划,其中用f数组来保存每个位置的最长上升子序列长度,并在每次更新时寻找当前的最大值。 2. 动态规划(Dynamic Programming,简称DP): - 动态规划是一种算法思想,用于求解具有...
3. **最长上升子序列 (LIS)**:对于一个序列S,其最长上升子序列是指S中的一个子序列,该子序列是严格递增的,且长度最长。 #### 三、问题定义 假设我们有两个字符串(或整数序列)a和b,我们的目标是找到这两个...
- 在完成上述步骤后,`dp`数组中的最大值即为整个数组的最长上升子序列的长度。 #### 四、Python代码示例 以下是一个用Python实现的LIS问题的动态规划解法示例: ```python def length_of_lis(nums): if not ...
首先,初始化数组f,表示每个位置的最长上升子序列长度,初始所有值为1。然后,遍历序列,对于每个元素i,再次遍历之前的元素j,如果j小于i且a[j]小于a[i],并且f[j]+1大于f[i],则更新f[i]为f[j]+1。最后,找出f...
3. 最后,dp数组中的最大值即为最长上升子序列的长度。 除了动态规划,还可以使用二分查找来优化解决方案。这种方法称为二分查找法+单调队列。维护一个单调递减的队列,每次在队列中插入新元素时,如果新元素小于...
An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 252 245 250 其中最长序列为: 300 275 200 138 ...
给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。 说明: 可能会有多种最长上升子序列的组合,你只需要...
3. 最后dp数组中的最大值即为最长上升子序列的长度。 在JavaScript中实现这个算法,可以使用以下代码示例: ```javascript function lengthOfLIS(nums) { if (nums.length === 0) return 0; let dp = new ...
初始化时,`c[0][0]`设置为0,因为没有元素的公共子序列长度为0。同时,边界条件`c[i][0]`和`c[0][j]`都设为0,表示只有一个序列时,LCS的长度自然为0。 接下来的双层循环是核心部分,用于计算每个`c[i][j]`的值。...
- 如果`dp[i] [j] + 1`,则更新`dp[i] = dp[j] + 1`,表示以`nums[i]`为结尾的最长上升子序列长度更新为`dp[j] + 1`。 3. 在遍历结束后,`dp`数组中的最大值即为最长上升子序列的长度。 在JavaScript中,代码可能...
在LeetCode的第300题“最长上升子序列”中,目标是找出给定无序整数数组中的最长上升子序列(Longest Increasing Subsequence, LIS)的长度。上升子序列是指序列中的元素逐个严格递增,但不一定是连续的。例如,对于...
要注意的是,`D[]` 数组在算法结束时并不直接给出最长上升子序列,而是记录了长度为 `k` 的最长上升子序列的最小末尾元素。为了获得实际的子序列,我们需要回溯数组 `D[]` 和原始序列 `A[]`。 总的来说,解决最长不...
最长上升子序列问题可以这样定义:给定一个无序的整数数组,任务是找到该数组中一个最长的子序列,使得这个子序列中的元素从左到右是严格递增的...最后,我们遍历dp数组,找到其中的最大值,即为最长上升子序列的长度。