The problem of finding the longest increasing subsequence (LIS) of a given array of integers is a classic dynamic programming problem. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For example, given the array [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101], so the length is 4.
The idea is to use an array to store the length of the LIS ending at each index of the input array, and then find the maximum value in that array. The algorithm can be summarized as follows:
Here is a possible C++ implementation of this algorithm:
#include <iostream>
#include <vector>
using namespace std;
int lengthOfLIS(vector<int> &nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
// Initialize an array to store LIS ending at each position.
vector<int> dp(n, 1);
// Initialize the maximum length of the LIS to 1.
int maxLength = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
// Update the LIS ending at position i.
dp[i] = max(dp[i], dp[j] + 1);
}
}
// Update the maximum length.
maxLength = max(maxLength, dp[i]);
}
return maxLength;
}
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
int result = lengthOfLIS(nums);
cout << "Length of LIS: " << result << endl; // 4
return 0;
}
This solution has a time complexity of O(n^2), where n is the size of the input array. This is because we use two nested loops to compare each element with all previous elements, resulting in a quadratic time complexity.
The space complexity is O(n) because we use an additional array dp of the same length as input array to store the lengths of the longest increasing subsequences ending at each position in the array.
There are more efficient solutions that can achieve a time complexity of O(nlogn), such as using binary search or segment tree, but they are more complex and require more coding. You can find more details and explanations about these solutions on various resources.