对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度,这里的子序列定义为这样一个序列U1,U2...,其中Ui < Ui+1,且A[Ui] < A[Ui+1]。
给定一个数字序列A及序列的长度n,请返回最长上升子序列的长度。
测试样例:
[2,1,4,3,1,5,6],7
返回:4
import java.util.*; public class AscentSequence { public int findLongest(int[] A, int n) { return getdp(A); } public int getdp(int[] arr) { int[] dp = new int[arr.length]; int[] ends = new int[arr.length]; ends[0] = arr[0]; dp[0] = 1; int right = 0; int len = 1; for (int i = 1; i < arr.length; i++) { int l = 0; int r = right; while (l <= r) { int mid = (l+r)/2; if (arr[i] > ends[mid]) { l = mid+1; } else { r = mid-1; } } right = Math.max(right, l); len = Math.max(l+1, len); ends[l] = arr[i]; dp[i] = l + 1; } return len; // return dp; } }
相关推荐
这是我这两天才完成的原创代码,就是比较经典的求一个随机序列的最长递增子序列问题。例如: n=5 随机序列为 5 1 4 2 3,正确输出为1 2 3,即长度为3的递增子序列。里面附带实验详细说明,感兴趣的可以下来参考。 ...
求一个由n个整数组成的整数序列的最长递增子序列。一个整数序列的递增子序列可以是序列中非连续的数按照原序列顺序排列而成的。 最长递增子序列是其递增子序列中长度最长的。
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
动态规划最长递增子序列 已经实现 请大家赐教
最长子序列 什么是最长递增子序列呢? 问题描述如下: 设L=,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=,ak2,…,akm>,其中k1…且aK1…。求最大的m值
最长递增子序列LCS的实现C源码,大学算法导论课程实验
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 Visual Studio 2012 项目包 使用4种不同的方法实现最长递增子序列
最长递增子序列问题是一个很基本、较常见的小问题,但这个问题的求解方法却并不那么显而易见,需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想,...
算法课实验代码,包括整数划分、各类排序、最长递增子序列、幻方矩阵等试验
贪心算法、动态规划实现最长递增子序列的求取(MFC编程)。
动态规划:最长单调递增子序列 A numeric sequence of ai is ordered if a1 (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 , sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. ...
中科大软件学院 算法导论课程实验 正式题目二 最长递增子序列 实验报告 使用4种不同的方式实现最长递增子序列
中国科学技术大学软件学院《算法设计与分析》实验题目四
给你一个整数数组 nums ,找到...解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。 示例 2: 输入:nums = [0,1,0,3,2,3] 输出:4 示例 3: 输入:nums = [7,7,7,7,7,7,7] 输出:1 参数范围: 1 -104 [i] <=104
最长递增子序列的另外一种C语言实现代码,大学算法导论课程实验
C++的课程作业,一个简单的程序,用dev就能直接运行,老师应该不会太仔细检查,糊弄一下肯定没事的,不过最好能自己看懂就是了
包括排序 最长递增子序列 红黑树三个相关程序
这是递增子序列的java实现版 希望对大家有所启迪