Find the length of the longest strictly increasing subsequence: numbers taken from the array in order (not necessarily next to each other), each bigger than the one before.
Input
The first line has n (1 ≤ n ≤ 300). The second line has the n numbers.
Output
The length of the longest strictly increasing subsequence.
Examples
Example 1 · Input
8 3 10 2 1 20 4 6 7
Expected output
4
Example 2 · Input
4 5 5 5 5
Expected output
1
Hints
Hint 1
best[i] = 1 + the largest best[j] with j < i and a[j] < a[i] (or 1 if there is none).
Hint 2
The answer is the largest best[i].
Hint 3
Strictly increasing: equal numbers do not count.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
vector<int> best(n, 1);
int answer = 1;
for (int i = 0; i < n; i++) {
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];
}
cout << answer << "\n";
return 0;
}