Longest Increasing Subsequence Solution (LIS) – LeetCode Solution [Medium]

Problem

Given an integer array arr, return the length of the longest strictly increasing subsequence. A strictly increasing sequence is a sequence such that all elements of the sequence are sorted in increasing order.

Note: In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence {A, B, D} is a subsequence of {A, B, C, D, E, F} obtained after removal of elements C, E and F.

Example 1:

Input: arr = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

LeetCode Problem Link

This problem could be solved by Dynamic programming in O(n²) time complexity and O(n) auxiliary space.

Optimal Substructure

An optimal solution to problem contain optimal solution to subproblems. To consider all subsequence of array elements, 2 cases for every element arises:

1. Element is included in optimal set
2. Element is not included in optimal set

Therefore, longest subsequence obtained from n items is maximum of the following:

1. The longest subsequence obtained by n-1 elements, excluding nth element.
2. nth element + longest subsequence obtained by n-1 elements

Then, LIS(i) can be recursively written as: 

if LIS[i] < LIS[j] + 1
  LIS(i) = 1 + LIS[j] where 0 < j < i and arr[j] < arr[i];
else 
  LIS(i) = 1, if no such j exists.
ans = MAX(ans, LIS[i])

Code Implementation

//
//  main.cpp
//  Longest Increasing Subsequence (LIS)
//
//  Created by Himanshu on 17/09/21.
//

#include <iostream>
using namespace std;
const int N = 8;

void LIS (int A[]) {
    int LIS[N], sol = 1;
    
    
    for (int i=0; i<N; i++) {
        LIS[i] = 1;
        
        for (int j=0; j<i; j++) {
            if (A[i] > A[j] && LIS[i] < LIS[j]+1) {
                LIS[i] = LIS[j] + 1;
            }
        }

        sol = max(sol, LIS[i]);
    }
    
    cout<<"Length of Longest Increasing Subsequence (LIS) is: "<<sol<<endl;
    
}
 
int main() {
    int A[N] = {10, 9, 2, 5, 3, 7, 101, 18};
    LIS(A);
}

Output:

Length of Longest Increasing Subsequence (LIS) is: 4

Here’s a working example: Ideone