Pick numbers from a list, keeping their order, so that each is bigger than the last. How many can you pick?
What to build
A dynamic program that finds the length of the longest strictly increasing subsequence.
Requirements
- Define
best[i]as the length of the best subsequence ending at indexi. - Build each value from the earlier positions.
- Print the largest value.
Input
The first line has n. The second line has the n numbers.
Output
The length of the longest strictly increasing subsequence.
Constraints
1 ≤ n ≤ 300.
Example
Input:
8
10 9 2 5 3 7 101 18
Output:
4
Why it works
A subsequence ending at i has some previous number at j with a smaller value, and what comes before it is the best subsequence ending at j. Trying every j covers all the possibilities, in O(n²) time.
Examples
8 10 9 2 5 3 7 101 18
4
6 0 1 0 3 2 3
4
Hints
Hint 1
Let `best[i]` be the length of the longest increasing subsequence that ends exactly at position `i`.
Hint 2
Look at every earlier position `j` where `a[j] < a[i]`, and extend the best one.
Hint 3
The answer is the largest value in `best`, and not always the last one.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, a[300], best[300];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int answer = 0;
for (int i = 0; i < n; i++) {
best[i] = 1;
for (int j = 0; j < i; j++)
if (a[j] < a[i] && best[j] + 1 > best[i]) best[i] = best[j] + 1;
if (best[i] > answer) answer = best[i];
}
printf("%d\n", answer);
return 0;
}