Longest Increasing Subsequence

BabbleDay posted @ 2013年4月20日 15:07 in 刷题防身 , 1464 阅读

Longest Increasing Subsequence

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Given a sequence $a_1, a_2, \ldots, a_n$ , find the largest subset such that for every $i < j$ , $a i < a j$ .

O(nlogn) solution

Let $A i, j$ be the smallest possible tail out of all increasing subsequences of length $j$ using elements $a_1, a_2, a_3, \ldots, a_i$ .
$A i, j$ 在这里表示原数组 $a_1, a_2, a_3, \ldots, a_i$ 里长度为j的递增子序列的可能的最小的末尾（例：对j=2有“14”和“13”则 $A i,2$ 表示3）
for any particular $i$ , $A_{i,1} < A_{i,2} < \ldots < A_{i,j}$ 这是观察所得规律，因其单增，故可用二分法
This suggests that if we want the longest subsequence that ends with $a i + 1$ , we only need to look for a j such that $A i, j < a i + 1 < = A i, j + 1$ and the length will be $j + 1$ .

Notice that in this case, $A i + 1, j + 1$ will be equal to $a i + 1$ , and all $A i + 1, k$ will be equal to $A i, k$ for $k \ne j + 1$ .

Furthermore, there is at most one difference between the set $A i$ and the set $A i + 1$ , which is caused by this search.

Since $A$ is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single $a_1, a_2, \ldots, a_n$ .

Further explain:--GONG Zhi Tao 11:19, 1 August 2012 (EDT)

We have elements: $a_1, a_2, a_3, \ldots, a_i$ .

And we have a longest increasing subsequences of them: $A_{i,1} < A_{i,2} < \ldots < A_{i,j}$ , for any $A i, k (1 < = k < = j)$ you could not find a smaller alternative.

Now we have a new element: $a i + 1$

What we can do about it:

1. insert it at the back if $A i, j < a i + 1$ , where we will have a longer one;

2. make it an alternative for $A i, k$ if $A_{i,k-1} < a_{i+1}\ AND\ a_{i+1} <= A_{i,k}$

Alternative means that we MIGHT get longer ones if using the new element.

http://blog.csdn.net/linulysses/article/details/5559262

具体实现代码，来自algorithmist

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
	vector<int> p(a.size());
	int u, v;
 
	if (a.empty()) return;
 
	b.push_back(0);
 
	for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
		if (a[b.back()] < a[i]) 
                {
			p[i] = b.back();
			b.push_back(i);
			continue;
		}
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
		for (u = 0, v = b.size()-1; u < v;) 
                {
			int c = (u + v) / 2;
			if (a[b[c]] < a[i]) u=c+1; else v=c;
		}
 
                // Update b if new value is smaller then previously referenced value 
		if (a[i] < a[b[u]]) 
                {
			if (u > 0) p[i] = b[u-1];
			b[u] = i;
		}	
	}
 
	for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
	int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
	vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
	vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
	for (size_t i = 0; i < lis.size(); i++)
		printf("%d ", seq[lis[i]]);
        printf("\n");    
 
	return 0;
}

[回复]

NCERT Exemplar Solu 说:
2023年9月26日 22:08

Here you will get the NCERT Class 7 Exemplar Problems and Solutions 2024 for All Pdf Chapters, All the Questions are Provided with an easy and Logical Explanation so as to give Students Understanding of the NCERT Exemplar Solutions for 7th 2024 Exemplar Problems.We Suggest you to go Through NCERT 7th Class Exemplar Problems 2024 and solve them before you see their Answers, Practicing these Exemplar Solutions will help you a lot in your School Exam, All Important Exemplar Solutions for Class 7 Given here are as per Latest Exemplar Solutions & Exercises of NCERT, Also these NCERT 7 Class Important Questions.

BabbleDay's Blog

Happy Coding

BabbleDays

分类

最新评论

最新留言

链接

RSS

功能

Longest Increasing Subsequence