Longest Increasing Subsequence in C++

This document provides a C++ program to find the longest increasing subsequence (LIS) in an array. The LIS is a subsequence of a given sequence where the subsequence’s elements are sorted in increasing order. This problem is commonly solved using dynamic programming.

Program Explanation

The following C++ program uses dynamic programming to find the longest increasing subsequence:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Function to find the length of the longest increasing subsequence.
 * @param nums Vector of integers representing the array.
 * @return Length of the longest increasing subsequence.
 */
int lengthOfLIS(const vector<int> &nums) {
    if (nums.empty()) return 0;

    vector<int> dp(nums.size(), 1);

    for (size_t i = 1; i < nums.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

/**
 * Main function to execute the program.
 */
int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};

    int length = lengthOfLIS(nums);
    cout << "Length of the Longest Increasing Subsequence: " << length << endl;

    return 0;
}
    

Program Structure

1. Include Headers: The program includes necessary headers such as <iostream> for input/output operations, <vector> for using the vector container, and <algorithm> for using standard algorithms like max_element.
2. lengthOfLIS Function: This function computes the length of the longest increasing subsequence.
   • dp: A vector that stores the length of the longest increasing subsequence ending at each index.
   • The function iterates over each element and updates the dp vector based on previous values to ensure it captures the longest subsequence.
3. Main Function: This function initializes an array, calls lengthOfLIS, and prints the result.

Explanation

The dynamic programming approach maintains a dp array where dp[i] represents the length of the longest increasing subsequence ending at index i. The algorithm iterates over each element and updates the dp values by checking all previous indices. The maximum value in the dp array at the end of the iteration gives the length of the longest increasing subsequence.