Longest Increasing Subsequence

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:

• Initialize an array dp of the same size as the input array, and fill it with 1. This means that the LIS ending at any index is at least 1 (the element itself).
• Loop from the second element to the last element of the input array, and for each element, loop from the first element to the current element.
• If the current element is greater than the previous element, then update dp[i] to be the maximum of dp[i] and dp[j] + 1, where j is the index of the previous element. This means that we can extend the LIS ending at j by adding the current element, and we choose the maximum length among all possible extensions.
• After the loops, find the maximum value in dp and return it as the answer.

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.