1234567891011121314151617181920212223242526272829 |
- #include <bits/stdc++.h>
- using namespace std;
- typedef vector<int> VI;
- #define MAX_N 1000
- #include "LongestIncreasingSubsequence.cpp"
- void test1() {
- VI v = {3, 4, 7, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
- VI r = lis(v, true);
- for(int i = 0; i < r.size()-1; i++)
- assert(r[i] < r[i+1]);
- assert(r.size() == 10);
- }
- void test2() {
- VI v = {1, 2, 3, 4, 7, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
- VI r = lis(v, false);
- for(int i = 0; i < r.size()-1; i++)
- assert(r[i] <= r[i+1]);
- assert(r.size() == 12);
- }
- int main() {
- test1();
- test2();
- return 0;
- }
|