#include <vector>
#include <iostream>
#include <algorithm>
int longestIncreasingSubsequence(std::vector<int>& nums) {
int numssize = nums.size();
std::vector<int> length(numssize, 1); // length of LIS ending at index i
int maxLength = 1;
for (int i = 1; i < numssize; i++) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
length[i] = std::max(length[i], length[j] + 1);
}
}
maxLength = std::max(maxLength, length[i]);
}
return maxLength;
}
int main() {
std::vector<int> nums = {4, 5, 1, 10, 3, 9, 18, 19}; // 5, 10, 9, 18, 19
std::cout << "Length of LIS: " << longestIncreasingSubsequence(nums) << std::endl;
}
/*
run:
Length of LIS: 5
*/
