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

Given an integer array arr, return the length of the longest strictly increasing subsequence. 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.

Problem Statement:

https://leetcode.com/problems/longest-increasing-subsequence/

This problem could be solved by Dynamic programming in O(n^2) 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. 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:

https://ideone.com/SpZbqL