Back to the Training Home
Back to the Training Home
Lesson: 28
Problem: 1765
Title: Longest Ordered Subsequence
Difficulty Level: 3.0
Date: FEB 28, 2009
Site: http://acm.tju.edu.cn/toj/
To solve this problem you have to need to know a dynamic algorithm, LIS (Longest Increasing Subsequence).
Very simple and straight forward problem. Just apply the algorithm and get accepted.
Solution:
#include<stdio.h>
#define MAXN 1002
int A[MAXN], N;
int L[MAXN], P[MAXN];
void printPath(int x) {
if(P[x] == -1) {
printf("%d",x);
return;
}
printPath(P[x]);
printf(" %d",A[x]);
}
int doLIS() {
int i, j;
int longest = 0, last = 0;
for(i = 1; i<=N; i++) {
int max = 0;
int parent = -1;
for(j = i-1; j>=0; j--) {
if(A[i] > A[j]) {
if(L[j] > max) {
max = L[j];
parent = j;
}
}
}
L[i] = max+1;
P[i] = parent;
if(L[i] > longest) {
longest = L[i];
last = i;
}
}
printf("%d\n",longest);
return longest;
}
int main() {
int i;
scanf("%d",&N);
A[0] = 0;
for(i = 1; i<= N; i++) {
scanf("%d",&A[i]);
}
doLIS();
return 0;
}