Longest Increasing Subsequence
The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.
注意题目要求:
1 所选的数值不必连续,可以间隔, 但是顺序不能乱
2 其中的间隔不用计算,只计算所选数的长度就可以
思路:
1 从最小两个开始计算。
2 计算i个数值的时候,只需要比较A[i]数值和i前所有数值,只要A[i]比任何一个数值A[j]大,那么动态规划表v[i]就在选取v[j] +1 和v[i]最大的值填上
v[j]+1表示在j个数值之前的最长递增子序列数是v[j],+1表示加上第i个值A[i],那么递增子序列就增加了1.
动态规划法很好解决:
int longestIncreaseSubsequence(int A[], int n)
{
vector<int> v(n, 1);
int maxL = 1;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (A[i] > A[j]) v[i] = max(v[i], v[j]+1);
maxL = max(maxL, v[i]);
}
}
return maxL;
}
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 10 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d\n", longestIncreaseSubsequence( arr, n ));
system("pause");
return 0;
}
测试例子的答案为4
分享到:
相关推荐
前端工程师面试
前端工程师面试
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
LMS Longest Monotonically Increasing Sequence Algorithm
最长公共子序列演示程序,算法分析与设计,动态规划算法
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
Brian Dean 在MIT教算法课录制的10个动态规划问题的视频动画。 包含 ...- longest increasing subsequences - making changes - maximum value contiguous subsequences - optimal strategy for a game
自述文件 该自述文件通常会记录启动和运行应用程序所需的所有步骤。 您可能要讲的内容: Ruby版本 系统依赖 配置 数据库创建 数据库初始化 如何运行测试套件 服务(作业队列,缓存服务器,搜索引擎等) ...
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...