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(n2) 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

Leave a Reply

Your email address will not be published. Required fields are marked *