A naive approach to solve this problem is to generate all the possible subsequences (using Power Set or Recursion method), check if the subsequence is increasing and then store the longest among them. Clearly, this approach will not be a useful approach for the given problem as it will end up taking O(2^N), where N is the number of elements in the given array, i.e., exponential time complexity.

Recusion

Intuition:

The idea is to generate all possible increasing subsequences and find the length of the longest among them. As we need to find all possible subsequences, recusion can be used to solve the problem.

Approach:

Steps to form the recursive solution:

Express the problem in terms of indices: Let us define a function f(ind) that represents the length of the Longest Increasing Subsequence (LIS) starting from ind. Ultimately, the result will be the f(0).
The problem is now reduced to calculating f(0).
Try all possible choices for each index: At each index ind, we consider whether the current element should extend a previous subsequence or not. This gives an idea to introduce another parameter prev_ind in the function such that the following two possibilities arise:
- Not Take case (If arr[prev_ind] >= arr[ind]): In such case, the current element cannot be taken into consideration because the goal is to form an increasing subsequence. Since the element is not taken, the prev_ind remains the same and the call simply jumps to the next index i.e., f(ind+1, prev_ind).
- Take case (If arr[prev_ind] < arr[ind]): In such case, the current element can be added to the previously considered subsequence (ending at prev_ind) thus increasing the length of LIS by 1 and the call simply jumps to func(ind + 1, ind).
  
  Note that, the prev_ind is updated to ind, as now the ind becomes the last selected index for the further subsequence.
- Initial case when the subsequence is empty: Initially, when the function call begins, there is no element chosen for the subsequence. To mark this, prev_ind can be set as -1 representing that the current element will be the first element that will be taken into consideration.
  
  Hence, to get the answer, the initial function call must be f(0, -1).
Return the longest length of LIS found:After the take and notTake calls, the longest length of the subsequence found can be returned as the answer to the current function call.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

/* Function to return the length of LIS starting from 
index i with the element prev_ind element refers to
the previously selected element in the subsequence*/
func(int i, int prev_ind, int arr[]) {
    
    // Not Take case
    int notTake = func(i+1, prev_ind, arr);
    
    // Take case
    int take = 0;
    
    // If no element is chosen till now
    if(prev_ind == -1)
        take = func(i+1, i, arr) + 1;
    
    /* Else the current element can be 
    taken if it is strictly increasing */
    else if(arr[i] > arr[prev_ind])
        take = func(i+1, i, arr) + 1;
    
    // Return the maximum length obtained from both cases
    return max(take, notTake);
}

Base cases:

When the function call reaches the last index, the base case will be called and there will be two cases:

Take case: If the last index element is greater than the prev_ind element in the subsequnce or if the last index element is the first element in the subsequence, it can be taken in the subsequence and 1 can be returned.
Not Take case: Otherwise, the last index element can not be considered and 0 can be returned.

Solution (Recursive):

Note that submitting the following solution will result in Time Limit Exceeded.

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to return the length of LIS starting from 
    index i with the element prev_ind element refers to
    the previously selected element in the subsequence*/
    int func(int i, int prevInd, vector<int> &arr) {
        
        // base case
        if(i == arr.size() - 1) {
            if(prevInd == -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // Not Take case
        int notTake = func(i+1, prevInd, arr);
        
        int take = 0; // Take case
        
        // If no element is chosen till now
        if(prevInd == -1)
            take = func(i+1, i, arr) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if(arr[i] > arr[prevInd])
            take = func(i+1, i, arr) + 1;
        
        // Return the maximum length obtained from both cases
        return max(take, notTake);
    }
    
public:
    /* Function to find the longest increasing 
    subsequence in the given array */
    int LIS(vector<int>& nums) {
        return func(0, -1, nums);
    }    
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}
class Solution {
    private int func(int i, int prevInd, int[] arr) {
        
        // base case
        if (i == arr.length - 1) {
            if (prevInd == -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // Not Take case
        int notTake = func(i + 1, prevInd, arr);
        
        int take = 0; // Take case
        
        // If no element is chosen till now
        if (prevInd == -1)
            take = func(i + 1, i, arr) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if (arr[i] > arr[prevInd])
            take = func(i + 1, i, arr) + 1;
        
        // Return the maximum length obtained from both cases
        return Math.max(take, notTake);
    }
    
    public int LIS(int[] nums) {
        return func(0, -1, nums);
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        int lengthOfLIS = sol.LIS(nums);
        
        System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
    }
}
class Solution:
    def func(self, i, prevInd, arr):
        # base case
        if i == len(arr) - 1:
            if prevInd == -1 or arr[prevInd] < arr[i]:
                return 1
            return 0
        
        # Not Take case
        notTake = self.func(i + 1, prevInd, arr)
        
        take = 0  # Take case
        
        # If no element is chosen till now
        if prevInd == -1:
            take = self.func(i + 1, i, arr) + 1
        
        # Else the current element can be 
        # taken if it is strictly increasing
        elif arr[i] > arr[prevInd]:
            take = self.func(i + 1, i, arr) + 1
        
        # Return the maximum length obtained from both cases
        return max(take, notTake)
    
    def LIS(self, nums):
        return self.func(0, -1, nums)


if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    
    # Creating an object of Solution class
    sol = Solution()
    lengthOfLIS = sol.LIS(nums)
    
    print("The length of the LIS for the given array is:", lengthOfLIS)
class Solution {
    func(i, prevInd, arr) {
        // base case
        if (i === arr.length - 1) {
            if (prevInd === -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // Not Take case
        let notTake = this.func(i + 1, prevInd, arr);
        
        let take = 0; // Take case
        
        // If no element is chosen till now
        if (prevInd === -1)
            take = this.func(i + 1, i, arr) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if (arr[i] > arr[prevInd])
            take = this.func(i + 1, i, arr) + 1;
        
        // Return the maximum length obtained from both cases
        return Math.max(take, notTake);
    }
    
    LIS(nums) {
        return this.func(0, -1, nums);
    }
}

const nums = [10, 9, 2, 5, 3, 7, 101, 18];

// Creating an object of Solution class
const sol = new Solution();
const lengthOfLIS = sol.LIS(nums);

console.log("The length of the LIS for the given array is:", lengthOfLIS);

Complexity Analysis:

Time Complexity: O(2^N), where N represents the number of elements in the given array
In each function call, two recursive calls are made (take and not take) resulting in an exponential time complexity.

Space Complexity: O(N), because of the recursion stack space.

Memoization

If you draw the recursion tree, you will see that there are overlapping subproblems. Hence the DP approache can be applied to the recursive solution to optimise it.

Steps to convert the recursive solution to the Memoization solution:

Declare a dp array of size [n][n]: There are two states of dp which are:
- ind: which can go from 0 to n-1, requiring a total of n indices.
- prev_ind: which can go from -1 to n-2, requiring a total of (n-2 -(-1) +1) or n states.
Important:
Note that there is no index as -1, hence, to store the state (prev_ind = -1), it is required to do a co-ordinate shift. We can map the -1 index to 0, 0 index to 1, and so on....

Hence, a 2D dp array is needed where dp[ind][prev_ind+1] stores the result of the function call func(ind, prev_ind). The dp array stores the calculations of subproblems hence it is initialized with -1, to indicate that no subproblem has been solved yet.
While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet (the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array before returning the function call.

Note

Note that submitting the following code will throw a runtime error because of the tight constraints set for the problem. N can go upto 10⁵ and declaring a 2D dp of size N*N will require 10¹⁰ space causing Memory Limit Exceeded resulting in runtime error.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to return the length of LIS starting from 
    index i with the element prev_ind element refers to
    the previously selected element in the subsequence*/
    int func(int i, int prevInd, vector<int> &arr, vector<vector<int>> &dp) {
        
        // base case
        if(i == arr.size() - 1) {
            if(prevInd == -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // If subproblem is already calculated
        if(dp[i][prevInd + 1] != -1) return dp[i][prevInd + 1];
        
        // Not Take case
        int notTake = func(i+1, prevInd, arr, dp);
        
        int take = 0; // Take case
        
        // If no element is chosen till now
        if(prevInd == -1)
            take = func(i+1, i, arr, dp) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if(arr[i] > arr[prevInd])
            take = func(i+1, i, arr, dp) + 1;
        
        // Return the maximum length obtained from both cases
        return dp[i][prevInd + 1] = max(take, notTake);
    }
    
public:
    /* Function to find the longest increasing 
    subsequence in the given array */
    int LIS(vector<int>& nums) {
        int n = nums.size();
        
        // DP array
        vector<vector<int>> dp(n, vector<int>(n+1, -1));
        
        return func(0, -1, nums, dp);
    }    
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to return the length of LIS starting from 
    index i with the element prev_ind element refers to
    the previously selected element in the subsequence */
    private int func(int i, int prevInd, int[] arr, int[][] dp) {
        
        // base case
        if (i == arr.length - 1) {
            if (prevInd == -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // If subproblem is already calculated
        if (dp[i][prevInd + 1] != -1) return dp[i][prevInd + 1];
        
        // Not Take case
        int notTake = func(i + 1, prevInd, arr, dp);
        
        int take = 0; // Take case
        
        // If no element is chosen till now
        if (prevInd == -1)
            take = func(i + 1, i, arr, dp) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if (arr[i] > arr[prevInd])
            take = func(i + 1, i, arr, dp) + 1;
        
        // Return the maximum length obtained from both cases
        dp[i][prevInd + 1] = Math.max(take, notTake);
        return dp[i][prevInd + 1];
    }
    
    /* Function to find the longest increasing 
    subsequence in the given array */
    public int LIS(int[] nums) {
        int n = nums.length;
        
        // DP array
        int[][] dp = new int[n][n + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        
        return func(0, -1, nums, dp);
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        int lengthOfLIS = sol.LIS(nums);
        
        System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
    }
}
class Solution:
    # Function to return the length of LIS starting from 
    # index i with the element prev_ind element refers to
    # the previously selected element in the subsequence
    def func(self, i, prevInd, arr, dp):
        
        # base case
        if i == len(arr) - 1:
            if prevInd == -1 or arr[prevInd] < arr[i]:
                return 1
            return 0
        
        # If subproblem is already calculated
        if dp[i][prevInd + 1] != -1:
            return dp[i][prevInd + 1]
        
        # Not Take case
        notTake = self.func(i + 1, prevInd, arr, dp)
        
        take = 0  # Take case
        
        # If no element is chosen till now
        if prevInd == -1:
            take = self.func(i + 1, i, arr, dp) + 1
        
        # Else the current element can be 
        # taken if it is strictly increasing
        elif arr[i] > arr[prevInd]:
            take = self.func(i + 1, i, arr, dp) + 1
        
        # Return the maximum length obtained from both cases
        dp[i][prevInd + 1] = max(take, notTake)
        return dp[i][prevInd + 1]
    
    # Function to find the longest increasing 
    # subsequence in the given array
    def LIS(self, nums):
        n = len(nums)
        
        # DP array
        dp = [[-1] * (n + 1) for _ in range(n)]
        
        return self.func(0, -1, nums, dp)

# Main
if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    
    # Creating an object of Solution class
    sol = Solution()
    lengthOfLIS = sol.LIS(nums)
    
    print(f"The length of the LIS for the given array is: {lengthOfLIS}")
class Solution {
    /* Function to return the length of LIS starting from 
    index i with the element prev_ind element refers to
    the previously selected element in the subsequence */
    func(i, prevInd, arr, dp) {
        // base case
        if (i === arr.length - 1) {
            if (prevInd === -1 || arr[prevInd] < arr[i]) return 1;
            return 0;
        }
        
        // If subproblem is already calculated
        if (dp[i][prevInd + 1] !== -1) return dp[i][prevInd + 1];
        
        // Not Take case
        let notTake = this.func(i + 1, prevInd, arr, dp);
        
        let take = 0; // Take case
        
        // If no element is chosen till now
        if (prevInd === -1)
            take = this.func(i + 1, i, arr, dp) + 1;
        
        /* Else the current element can be 
        taken if it is strictly increasing */
        else if (arr[i] > arr[prevInd])
            take = this.func(i + 1, i, arr, dp) + 1;
        
        // Return the maximum length obtained from both cases
        dp[i][prevInd + 1] = Math.max(take, notTake);
        return dp[i][prevInd + 1];
    }
    
    /* Function to find the longest increasing 
    subsequence in the given array */
    LIS(nums) {
        const n = nums.length;
        
        // DP array
        const dp = Array.from({ length: n }, () => Array(n + 1).fill(-1));
        
        return this.func(0, -1, nums, dp);
    }
}

// Main
const nums = [10, 9, 2, 5, 3, 7, 101, 18];

// Creating an object of Solution class
const sol = new Solution();
const lengthOfLIS = sol.LIS(nums);

console.log(`The length of the LIS for the given array is: ${lengthOfLIS}`);

Complexity Analysis:

Time Complexity: O(N²), where N is the size of the array
Because there will be a total of N*N states for which the function will be called.

Space Complexity: O(N²), because of the 2D dp array created taking O(N²) space and O(N) recursive stack space.

Pre-requisites: Lower bound

Intuition:

To solve the problem efficiently, a greedy approach can be used. Instead of creating new subsequences everytime, we can store the length of LIS as we process elements one by one in the array.

Understanding:

Consider the following array: nums = [1, 5, 7, 2, 3]
Let us try to find the length of Longest Increase Subsequence step by step taking a temporary array (initially temp is empty):

At i = 0: The element at index 0 (1) can be added to temp as it is the first element being added. Thus,
temp = [1]
At i = 1: The element at index 1 (5) can be added to the subsequence as it is greater than the last element in temp, i.e., Since 5 > 1,
temp = [1, 5]
At i = 2: The element at index 2 (7) can be added to the subsequence as it is greater than the last element in temp, i.e., Since 7 > 5,
temp = [1, 5, 7]
At i = 3: The element at index 3 is 2 which is not greater than the last element, i.e., 2 ≯ 7. Now we cannot add it to the back of the temp array to form an increasing subsequence. Instead, we must find its correct index at which it can be placed in the current subsequence.
This gives an idea of using Binary Search to find the index in the sorted temp array where the current element can be placed.

As per the current example, the element 2 must be stored in the temp and the correct index where it will be placed is index 1. Hence, the element at index 1 in the temp array is replaced with 2. Thus,
temp = [1, 2, 7]
Note that temp array does not explicitly store the Longest Increasing Subsequence. Instead, the length of temp tells us about the length of Longest Increasing Subsequence seen till the current index.
At i = 4: The element at index 4 is 3 which is not greater than the last element, i.e., 3 ≯ 7. Now we cannot add it to the back of the temp array to form an increasing subsequence. Instead, we must find its correct index at which it can be placed in the current subsequence.
As per the current example, the element 3 must be stored in the temp and the correct index where it will be placed is index 2. Hence, the element at index 2 in the temp array is replaced with 3. Thus,
temp = [1, 2, 3]

Role of Binary Search:

As we process each number in the input array:

If the current number is greater than the last number in temp: The LIS can be extended by adding the current number to the end of temp.
If the current number is smaller or equal to some number in temp: Replace the smallest number in temp that is greater than or equal to the current number. This ensures that temp remains as small as possible, leaving room for future elements to extend the sequence.

Now, in order to efficiently find where to place or replace the current number in temp, we use binary search (Lower Bound functionality).

Approach:

Maintain a temporary list to represent the smallest possible increasing subsequence formed so far.
Iterate through each element in the input array:
- If the current element is greater than the last element of the temporary list, append it to extend the subsequence.
- Otherwise, use binary search to find the position in the temporary list where the current element should replace an element to keep the subsequence valid and minimal.
The size of the temporary list at the end of the iteration represents the length of the longest increasing subsequence.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the longest increasing 
    subsequence in the given array */
    int LIS(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> temp;
        temp.push_back(nums[0]);
        
        // Iterate on the elements of the array
        for(int i=1; i < n; i++) {
            
            // If the current element can be added to the subsequence
            if(nums[i] > temp.back()) 
                temp.push_back(nums[i]); 
                
            // Otherwise
            else {
                // Index at which the current element must be placed
                int ind = lower_bound(temp.begin(), temp.end(), nums[i]) -
                          temp.begin();
                          
                // Place the current element in the subsequence
                temp[ind] = nums[i];
            }    
            
        }
        
        // Return the length of temporary subsequence created so far
        return temp.size();
    }    
};


int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    // Creating an object of Solution class
    Solution sol;
    int lengthOfLIS = sol.LIS(nums);
    
    cout << "The length of the LIS for the given array is: " << lengthOfLIS << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to find the longest increasing 
    subsequence in the given array */
    public int LIS(int[] nums) {
        int n = nums.length;
        
        List<Integer> temp = new ArrayList<>();
        temp.add(nums[0]);
        
        // Iterate on the elements of the array
        for (int i = 1; i < n; i++) {
            
            // If the current element can be added to the subsequence
            if (nums[i] > temp.get(temp.size() - 1)) 
                temp.add(nums[i]); 
                
            // Otherwise
            else {
                // Index at which the current element must be placed
                int ind = Collections.binarySearch(temp, nums[i]);
                if (ind < 0) ind = -(ind + 1);
                
                // Place the current element in the subsequence
                temp.set(ind, nums[i]);
            }    
        }
        
        // Return the length of temporary subsequence created so far
        return temp.size();
    }
}

class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // Creating an object of Solution class
        Solution sol = new Solution();
        int lengthOfLIS = sol.LIS(nums);
        
        System.out.println("The length of the LIS for the given array is: " + lengthOfLIS);
    }
}
class Solution:
    # Function to find the longest increasing 
    # subsequence in the given array
    def LIS(self, nums):
        n = len(nums)
        
        temp = []
        temp.append(nums[0])
        
        # Iterate on the elements of the array
        for i in range(1, n):
            
            # If the current element can be added to the subsequence
            if nums[i] > temp[-1]:
                temp.append(nums[i]) 
            
            # Otherwise
            else:
                # Index at which the current element must be placed
                ind = self.lower_bound(temp, nums[i])
                
                # Place the current element in the subsequence
                temp[ind] = nums[i]
        
        # Return the length of temporary subsequence created so far
        return len(temp)

    # Binary search to find the index of the smallest element >= target
    def lower_bound(self, temp, target):
        left, right = 0, len(temp) - 1
        while left <= right:
            mid = (left + right) // 2
            if temp[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

# Example usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]

# Creating an object of Solution class
sol = Solution()
lengthOfLIS = sol.LIS(nums)

print("The length of the LIS for the given array is:", lengthOfLIS)
class Solution {
    /* Function to find the longest increasing 
    subsequence in the given array */
    LIS(nums) {
        let n = nums.length;
        
        let temp = [];
        temp.push(nums[0]);
        
        // Iterate on the elements of the array
        for (let i = 1; i < n; i++) {
            
            // If the current element can be added to the subsequence
            if (nums[i] > temp[temp.length - 1]) 
                temp.push(nums[i]); 
                
            // Otherwise
            else {
                // Index at which the current element must be placed
                let ind = this.lowerBound(temp, nums[i]);
                
                // Place the current element in the subsequence
                temp[ind] = nums[i];
            }    
        }
        
        // Return the length of temporary subsequence created so far
        return temp.length;
    }
    
    // Binary search to find the index of the smallest element >= target
    lowerBound(temp, target) {
        let left = 0, right = temp.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (temp[mid] < target) 
                left = mid + 1;
            else 
                right = mid - 1;
        }
        return left;
    }
}

// Example usage
let nums = [10, 9, 2, 5, 3, 7, 101, 18];

// Creating an object of Solution class
let sol = new Solution();
let lengthOfLIS = sol.LIS(nums);

console.log("The length of the LIS for the given array is:", lengthOfLIS);

Complexity Analysis:

Time Complexity: O(N*logN), where N is the size of the given array
Since the code leverages the Lower Bound function (implemented using binary search) it results is O(N*logN) complexity.

Space Complexity: O(N), to store the elements in the temp array.

Problem List

Longest Increasing Subsequence

Examples:

Constraints

Hints

Editorial

Recusion

Intuition:

Approach:

Steps to form the recursive solution:

Base cases:

Solution (Recursive):

Complexity Analysis:

Memoization

Steps to convert the recursive solution to the Memoization solution:

Important:

Note

Solution:

Complexity Analysis:

Intuition:

Understanding:

Role of Binary Search:

Approach:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code