988. Subsequence
Given a sequence, find the length of the
largest strictly increasing subsequence.
Input. First line contains the length n (1 ≤ n ≤ 1000)
of the sequence. The second line contains the sequence itself. All numbers are
integers not exceeding 10000 by absolute value.
Output. Print the
maximum length of strictly increasing subsequence.
|
Sample
input |
Sample
output |
|
6 3 29 5 5 28
6 |
3 |
SOLUTION
longest increasing
subsequence
Algorithm analysis
In this problem you must
find the length of the longest increasing subsequence (LIS).
Example
For the sample given, LIS can be {3, 5,
6} or {3, 5, 28}. The length of the LIS is 3.
Algorithm realization
Store the input
sequence in the array x. Declare an auxiliary array lis.
#define MAX 1001
int x[MAX], lis[MAX];
The main part of the program. Read the input sequence.
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&x[i]);
Carry out n iterations of the
algorithm.
for (len = i = 0; i < n; i++)
{
pos = lower_bound(lis,lis+len,x[i])
- lis;
if (pos < len) lis[pos] = x[i]; else lis[len++] = x[i];
}
Print the length of LIS.
printf("%d\n",len);
Algorithm realization – STL vector
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> x, lis;
int i, n, len, pos;
int main(void)
{
scanf("%d", &n);
x.resize(n);
for (i = 0; i < n; i++)
scanf("%d", &x[i]);
for (i = 0; i < n; i++)
{
pos = lower_bound(lis.begin(), lis.end(), x[i]) - lis.begin();
if (pos < lis.size())
lis[pos] = x[i]; else lis.push_back(x[i]);
}
printf("%d\n", lis.size());
return 0;
}
Algorithm realization – O(n2)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace
std;
vector<int> x, d;
int i, j, n, res;
int main(void)
{
scanf("%d",&n);
x.resize(n); d.resize(n);
for(i = 0; i
< n; i++)
{
scanf("%d",&x[i]);
d[i] = 1;
}
for (i = 0; i
< n; i++)
for (j = 0;
j < i; j++)
if (x[j]
< x[i]) d[i] = max(d[i],1 + d[j]);
res = *max_element(d.begin(),d.end());
printf("%d\n",res);
return 0;
}
Java realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
int x[] = new int[n];
for (int i = 0; i < n; i++)
x[i] = con.nextInt();
int lis[] = new int[n];
int len = 0;
for (int i = 0; i < n; i++)
{
int pos = Arrays.binarySearch(lis, 0, len, x[i]);
if(pos < 0) pos = - (pos + 1);
lis[pos] = x[i];
if(pos == len) len++;
}
System.out.println(len);
con.close();
}
}