C++ Program to Find the Longest Increasing Subsequence

by

Introduction

In the world of computer science, one common problem is finding the Longest Increasing Subsequence (LIS) in a given sequence. This problem is significant in various applications such as data analysis, bioinformatics, and pattern recognition. The Longest Increasing Subsequence is a subsequence that appears in the same order as the original sequence but is strictly increasing. In this article we will explore the concept of LIS, get the necessary prerequisites, and demonstrate three different C++ Program to Find the Longest Increasing Subsequence, each with explanations and outputs.

Prerequisites

Before diving into the code, it’s essential to have a basic understanding of the following:

  • C++ Programming: Familiarity with C++ syntax and standard library functions.
  • Dynamic Programming: Understanding of dynamic programming principles as one of the solutions involves this approach.
  • Algorithm Analysis: Basic knowledge of algorithm complexity to appreciate the efficiency of each solution.

Understanding Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem can be formally defined as follows: Given a sequence of integers, find the longest subsequence such that all elements of the subsequence are sorted in increasing order.

Example

Consider the sequence: [10, 22, 9, 33, 21, 50, 41, 60, 80]

The LIS for this sequence is [10, 22, 33, 50, 60, 80], which has a length of 6.

Formula and Approach

The problem can be approached using different techniques, including:

  1. Dynamic Programming: Building solutions to subproblems and combining them.
  2. Patience Sorting: Using binary search for efficient LIS calculation.

Each method has its own efficiency and complexity, which we will explore with examples.

Solutions and Examples

Solution 1: Dynamic Programming Approach to Find Longest Increasing Subsequence

Algorithm

  1. Initialize an array lis of the same length as the input sequence, with all elements set to 1.
  2. Iterate through the sequence, and for each element, find the LIS ending at that element.
  3. Update the lis array based on previous elements.

Code

C++
#include <iostream>
#include <vector>
#include <algorithm>

int LIS(std::vector<int> &arr) {
    int n = arr.size();
    std::vector<int> lis(n, 1);

    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
                lis[i] = lis[j] + 1;

    return *std::max_element(lis.begin(), lis.end());
}

int main() {
    std::vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    std::cout << "Length of LIS is " << LIS(arr) << std::endl;
    return 0;
}

Output

C++
Length of LIS is 6

Solution 2: Binary Search and Patience Sorting to Find Longest Increasing Subsequence

Algorithm

  1. Use a vector to store the end elements of the potential increasing subsequences.
  2. For each element in the sequence, use binary search to find its position in the vector.
  3. Replace the element at the found position with the current element.

Code

C++
#include <iostream>
#include <vector>
#include <algorithm>

int LIS(std::vector<int> &arr) {
    std::vector<int> lis;

    for (int x : arr) {
        auto it = std::lower_bound(lis.begin(), lis.end(), x);
        if (it == lis.end())
            lis.push_back(x);
        else
            *it = x;
    }

    return lis.size();
}

int main() {
    std::vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    std::cout << "Length of LIS is " << LIS(arr) << std::endl;
    return 0;
}

Output

C++
Length of LIS is 6

Solution 3: Recursive Approach with Memoization to Find Longest Increasing Subsequence

Algorithm

  1. Define a recursive function that returns the length of LIS ending at a given index.
  2. Use memoization to store results of subproblems to avoid redundant calculations.

Code

C++
#include <iostream>
#include <vector>
#include <algorithm>

int LISUtil(std::vector<int> &arr, int n, int &max_lis, std::vector<int> &dp) {
    if (dp[n] != -1) return dp[n];
    int res, max_ending_here = 1;

    for (int i = 1; i < n; i++) {
        res = LISUtil(arr, i, max_lis, dp);
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }

    dp[n] = max_ending_here;
    max_lis = std::max(max_lis, max_ending_here);
    return dp[n];
}

int LIS(std::vector<int> &arr) {
    int n = arr.size();
    int max_lis = 1;
    std::vector<int> dp(n+1, -1);

    LISUtil(arr, n, max_lis, dp);
    return max_lis;
}

int main() {
    std::vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    std::cout << "Length of LIS is " << LIS(arr) << std::endl;
    return 0;
}

Output

C++
Length of LIS is 6

Conclusion

Finding the Longest Increasing Subsequence is a classic problem in computer science, with applications in various fields. In this article, we explored three different approaches to solving the LIS problem in C++: using dynamic programming, binary search with patience sorting, and a recursive approach with memoization. Each method has its own merits and complexities, providing multiple avenues for solving the problem based on specific requirements and constraints. Understanding these approaches not only enhances problem-solving skills but also deepens the appreciation for algorithmic efficiency and optimization.