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

求最长升序序列

 
阅读更多

求一个序列的最长的升序序列,比如数组array[10]。

 

我的想法:

1. 以变量max_length记录最长的序列长度,以loc记录最长序列的位置,初始化都为0。

2. 设置变量temp_length=0,temp_loc=0,遍历每个元素array[i]{

      如果array[i]<=array[i+1],temp_length++;

      否则{

        判断temp_length与max_length大小,更新max_length和loc;

        temp_length=0,temp_loc=i;

      }

    }

3. 最后得到的就是loc和max_length就是最长子序列的位置和长度。

 

分享到:
评论

相关推荐

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

    在JavaScript编程领域,"最长上升子序列"(Longest Increasing Subsequence, LIS)是一个经典的算法问题,它在数组或序列中寻找一个具有最长连续递增顺序的子序列。这个题目通常出现在数据结构与算法的学习中,是...

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

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

    [转载]nlogn的最长子序列算法.rar_最长 排序_最长子序列

    在给定的一组序列或数组中,最长子序列是指一个非降序(或者非升序)的子序列,其长度最大。例如,在序列[3, 10, 2, 1, 20]中,非降序的最长子序列为[3, 10, 20],长度为3。 解决这个问题的经典算法之一是动态规划...

    数据结构考试题考试题经典题目

    4. **动态规划**:解决一些复杂问题时,通过将大问题分解为小问题,用已解决的小问题来构建大问题的解,如斐波那契数列、背包问题、最长公共子序列等。 5. **贪心算法**:在每一步选择当前最优解,以期达到全局最优...

    BOJ1093.rar_Windows编程_C/C++_

    最后,`dp`数组中的最大值即为所求的最长升序子序列的长度。 【标签】"Windows编程 C/C++" 表示解冑方案可能涉及Windows平台下的C或C++编程,这可能意味着程序的实现或测试环境是在Windows操作系统上。虽然这个问题...

    JavaScript实现找出数组中最长的连续数字序列

    7. 对parseResults中的所有序列进行排序,按照序列的长度升序排序。 8. 根据排序结果,取最长的连续数字序列作为最终结果。 另外,我们还需要理解该方法的参数说明和返回值。函数maxSequence接受两个参数:array和...

    最长子序列详解

    最长子序列问题是指在给定的一组序列(数组或字符串)中,找到一个非降序(或非升序)的最长子序列。这里的“子序列”是指原序列中去掉若干元素(可以是0个)后剩下的部分,但保持原有顺序不变。例如,对于数组 `[10...

    俄罗斯套娃信封问题(一维升序 二维降序)1

    然后,通过两个嵌套循环遍历所有信封,比较当前信封与之前所有信封的高度,如果当前信封的高度大于之前的某个信封,就更新`dp[i]`为以`i`结尾的最长递增子序列长度。最后,返回`dp`数组中的最大值,即为最长嵌套序列...

    二叉树的前,中,后序非递归,递归遍历,层次遍历,最长路径

    在二叉搜索树中,中序遍历会得到节点的升序序列。递归方法是先遍历左子树,再访问根节点,最后遍历右子树。非递归实现同样可以借助栈,但处理方式不同,需要在遇到叶子节点或左子树为空时才访问根节点。 3. **后序...

    算法与编程作业

    例如,对于数字1,7,5,3,9,可以找到{1,7,9},{1,5,9}等升序序列。 2. 解决方案:首先检查数字是否已经完全有序,如果是,则直接输出。否则,通过嵌套循环检查是否存在4个或3个升序排列,并在找到时输出最长...

    leetcode跳跃-DataStructureAndAlgorithm:数据结构理论知识&LeetCode

    因此,最终整个序列的最长升序子序列长度是dp数组中的最大值 dp通项为\( dp[i] = max(dp[i], dp[j] + 1), i &gt; j 且 num[i] &gt; nums[j] \) 双串, tips:用一个二维数组表示两个字符串对应的子串的公共子串的长度的...

    最长递增子序列

    首先,我们维护一个升序的dp数组,同时记录每个子序列的结束位置。当遍历原数组nums时,对于每个元素nums[i],我们查找dp数组中第一个大于等于nums[i]的位置,并更新dp值。这个查找过程可以使用二分查找算法加速。 ...

    JavaScript实现列出数组中最长的连续数

    在给定的编程问题中,任务是找到一个无序整数数组中的最长连续数字序列。提供的JavaScript函数`maxSequence`实现了这一功能。该函数接受两个参数:`array`(待处理的整数数组)和`step`(序列的步长,可选,默认为1...

    按键持续时间最长的键1

    给定一个字符串`keysPressed`,它表示测试序列中按键的顺序,以及一个升序排列的整数数组`releaseTimes`,表示每个键松开的时间。我们从0开始计时,每个键都在前一个键松开的时刻被按下。 题目中提到,按键的持续...

    合唱队形 解题报告 NOIP

    - **动态规划**:计算最长上升序列(LIS, Longest Increasing Subsequence)和最长下降序列(LDS, Longest Decreasing Subsequence)。 - **枚举分割点**:对于每个可能的分割点,计算左边LIS和右边LDS的长度。 -...

    408代码汇总1

    通过二路归并的思想,我们可以同时遍历两个升序序列S1和S2,每次选取较小的元素,直到遍历完n个元素。此时,选取的第n/2个元素就是两个序列的中位数。 ```c int Search_M(int S1[], int S2[], int n) { int i=j...

    lis.rar_lis

    描述中的 "求一组数的最长上升子序列,时间复杂度为O(nlogn)" 提到,我们需要找到一种高效的方法来解决这个问题,而这个方法的时间复杂度应该是线性对数级别的。这意味着我们不能简单地采用暴力枚举所有可能的子序列...

    任务(第1部分).docx

    在这个任务中,我们接收一个正整数序列,目标是找出序列中最长的连续自然数序列的长度。这可以通过维护两个变量来实现:当前连续序列的长度和最长序列的长度。遍历整个输入序列,如果当前数字比前一个数字大1,就...

    动态规划_李远韬.ppt

    以“最长上升子序列”为例,给定一个序列,目标是找到一个子序列,使得这个子序列是升序的且长度最大。在这个问题中,状态可以定义为`f[i]`,表示序列`a1, a2, ..., ai`中包含`ai`的最长上升子序列的长度。按照`i`的...

Global site tag (gtag.js) - Google Analytics