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:
- Element is included in optimal set
- Element is not included in optimal set
Therefore, longest subsequence obtained from n items is maximum of the following:
- Longest subsequence obtained by n-1 elements, excluding nth element.
- 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: