Home Binary Search Longest Increasing Subsequence using Memoization

Longest Increasing Subsequence using Memoization

Longest Increasing Sequence using Recursion:

Longest Increasing Subsequence using Dynamic Programming:

If noticed carefully, we can see that the above recursive solution also follows the overlapping subproblems property i.e., same substructure solved again and again in different recursion call paths. We can avoid this using the memoization approach.

We can see that each state can be uniquely identified using two parameters:

  • Current index (denotes the last index of the LIS) and
  • Previous index (denotes the ending index of the previous LIS behind which the arr[i] is being concatenated).

Below is the implementation of the above approach.

C++ 
// C++ code of memoization approach for LIS
#include <bits/stdc++.h>
using namespace std;

// To make use of recursive calls, this
// function must return two things:
// 1) Length of LIS ending with element
// arr[n-1].
// We use max_ending_here for this purpose
// Overall maximum as the LIS may end with
// an element before arr[n-1] max_ref is
// used this purpose.
// The value of LIS of full array of size
// n is stored in *max_ref which is
// our final result
int f(int idx, int prev_idx, int n, int a[],
      vector<vector<int> >& dp)
{
    if (idx == n) {
        return 0;
    }

    if (dp[idx][prev_idx + 1] != -1) {
        return dp[idx][prev_idx + 1];
    }

    int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
    int take = INT_MIN;
    if (prev_idx == -1 || a[idx] > a[prev_idx]) {
        take = 1 + f(idx + 1, idx, n, a, dp);
    }

    return dp[idx][prev_idx + 1] = max(take, notTake);
}

// Function to find length of
// longest increasing subsequence
int longestSubsequence(int n, int a[])
{
    vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1));
    return f(0, -1, n, a, dp);
}

// Driver program to test above function
int main()
{
    int a[] = { 3, 10, 2, 1, 20 };
    int n = sizeof(a) / sizeof(a[0]);

    // Function call
    cout << "Length of lis is " << longestSubsequence(n, a);
    return 0;
}
Java 
// A Memoization Java Program for LIS Implementation

import java.lang.*;
import java.util.Arrays;

class LIS {

    // To make use of recursive calls, this function must
    // return two things: 1) Length of LIS ending with
    // element arr[n-1]. We use max_ending_here for this
    // purpose 2) Overall maximum as the LIS may end with an
    // element before arr[n-1] max_ref is used this purpose.
    // The value of LIS of full array of size n is stored in
    // *max_ref which is our final result
    static int f(int idx, int prev_idx, int n, int a[],
                 int[][] dp)
    {
        if (idx == n) {
            return 0;
        }

        if (dp[idx][prev_idx + 1] != -1) {
            return dp[idx][prev_idx + 1];
        }

        int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
        int take = Integer.MIN_VALUE;
        if (prev_idx == -1 || a[idx] > a[prev_idx]) {
            take = 1 + f(idx + 1, idx, n, a, dp);
        }

        return dp[idx][prev_idx + 1]
            = Math.max(take, notTake);
    }

    // The wrapper function for _lis()
    static int lis(int arr[], int n)
    {
        // The function _lis() stores its result in max
        int dp[][] = new int[n + 1][n + 1];
        for (int row[] : dp)
            Arrays.fill(row, -1);

        return f(0, -1, n, arr, dp);
    }

    // Driver program to test above functions
    public static void main(String args[])
    {
        int a[] = { 3, 10, 2, 1, 20 };
        int n = a.length;

        // Function call
        System.out.println("Length of lis is " + lis(a, n));
    }
}

// This code is contributed by Sanskar.
Python 
# A Naive Python recursive implementation
# of LIS problem


import sys

# To make use of recursive calls, this
# function must return two things:
# 1) Length of LIS ending with element arr[n-1].
#     We use max_ending_here for this purpose
# 2) Overall maximum as the LIS may end with
#     an element before arr[n-1] max_ref is
#     used this purpose.
# The value of LIS of full array of size n
# is stored in *max_ref which is our final result


def f(idx, prev_idx, n, a, dp):

    if (idx == n):
        return 0

    if (dp[idx][prev_idx + 1] != -1):
        return dp[idx][prev_idx + 1]

    notTake = 0 + f(idx + 1, prev_idx, n, a, dp)
    take = -sys.maxsize - 1
    if (prev_idx == -1 or a[idx] > a[prev_idx]):
        take = 1 + f(idx + 1, idx, n, a, dp)

    dp[idx][prev_idx + 1] = max(take, notTake)
    return dp[idx][prev_idx + 1]

# Function to find length of longest increasing
# subsequence.


def longestSubsequence(n, a):

    dp = [[-1 for i in range(n + 1)]for j in range(n + 1)]
    return f(0, -1, n, a, dp)


# Driver program to test above function
if __name__ == '__main__':
    a = [3, 10, 2, 1, 20]
    n = len(a)

    # Function call
    print("Length of lis is", longestSubsequence(n, a))

# This code is contributed by shinjanpatra
C# 
// C# approach to implementation the memoization approach

using System;

class GFG {

    // To make use of recursive calls, this
    // function must return two things:
    // 1) Length of LIS ending with element arr[n-1].
    // We use max_ending_here for this purpose
    // 2) Overall maximum as the LIS may end with
    // an element before arr[n-1] max_ref is
    //  used this purpose.
    // The value of LIS of full array of size n
    // is stored in *max_ref which is our final result
    public static int INT_MIN = -2147483648;

    public static int f(int idx, int prev_idx, int n,
                        int[] a, int[, ] dp)
    {
        if (idx == n) {
            return 0;
        }
        if (dp[idx, prev_idx + 1] != -1) {
            return dp[idx, prev_idx + 1];
        }
        int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
        int take = INT_MIN;
        if (prev_idx == -1 || a[idx] > a[prev_idx]) {
            take = 1 + f(idx + 1, idx, n, a, dp);
        }

        return dp[idx, prev_idx + 1]
            = Math.Max(take, notTake);
    }

    // Function to find length of longest increasing
    // subsequence.
    public static int longestSubsequence(int n, int[] a)
    {
        int[, ] dp = new int[n + 1, n + 1];

        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                dp[i, j] = -1;
            }
        }
        return f(0, -1, n, a, dp);
    }

    // Driver code
    static void Main()
    {
        int[] a = { 3, 10, 2, 1, 20 };
        int n = a.Length;
        Console.WriteLine("Length of lis is "
                          + longestSubsequence(n, a));
    }
}

// The code is contributed by Nidhi goel.
Javascript 
/* A Naive Javascript recursive implementation
      of LIS problem */

      /* To make use of recursive calls, this
      function must return two things:
      1) Length of LIS ending with element arr[n-1].
          We use max_ending_here for this purpose
      2) Overall maximum as the LIS may end with
          an element before arr[n-1] max_ref is
          used this purpose.
      The value of LIS of full array of size n
      is stored in *max_ref which is our final result
      */

      function f(idx, prev_idx, n, a, dp) {
        if (idx == n) {
          return 0;
        }

        if (dp[idx][prev_idx + 1] != -1) {
          return dp[idx][prev_idx + 1];
        }

        var notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
        var take = Number.MIN_VALUE;
        if (prev_idx == -1 || a[idx] > a[prev_idx]) {
          take = 1 + f(idx + 1, idx, n, a, dp);
        }

        return (dp[idx][prev_idx + 1] = Math.max(take, notTake));
      }
      // Function to find length of longest increasing
      // subsequence.
      function longestSubsequence(n, a) {
        var dp = Array(n + 1)
          .fill()
          .map(() => Array(n + 1).fill(-1));
        return f(0, -1, n, a, dp);
      }

      /* Driver program to test above function */

      var a = [3, 10, 2, 1, 20];
      var n = 5;
      console.log("Length of lis is " + longestSubsequence(n, a));
      
      // This code is contributed by satwiksuman.

Output
Length of lis is 3

Time Complexity: O(N2)
Auxiliary Space: O(N2)

Longest Increasing Subsequence (LIS)

Given an array arr[] of size N, the task is to find the length of the Longest Increasing Subsequence (LIS) i.e., the longest possible subsequence in which the elements of the subsequence are sorted in increasing order.

Longest Increasing Subsequence

Examples:            

Input: arr[] = {3, 10, 2, 1, 20}
Output: 3
Explanation: The longest increasing subsequence is 3, 10, 20

Input: arr[] = {50, 3, 10, 7, 40, 80}
Output: 4
Explanation: The longest increasing subsequence is {3, 7, 40, 80}

Input: arr[] = {30, 20, 10}
Output:1
Explanation: The longest increasing subsequences are {30}, {20} and (10)

Input: arr[] = {10, 20, 35, 80}
Output: 4
Explanation: The whole array is sorted

Similar Reads

Longest Increasing Sequence using Recursion:

The idea to do traverse the input array from left to right and find length of the Longest Increasing Subsequence (LIS) ending with every element arr[i]. Let the length found for arr[i] be L[i]. At the end we return maximum of all L[i] values. Now the question arises, how do we compute L[i]? For this, we us recursion, we consider all smaller elements on left of arr[i], recursively compute LIS value for all the smaller elements on left, take the maximum of all and add 1 to it. If there is no smaller element on left of an element, we return 1....

Longest Increasing Subsequence using Memoization:

If noticed carefully, we can see that the above recursive solution also follows the overlapping subproblems property i.e., same substructure solved again and again in different recursion call paths. We can avoid this using the memoization approach. We can see that each state can be uniquely identified using two parameters: Current index (denotes the last index of the LIS) andPrevious index (denotes the ending index of the previous LIS behind which the arr[i] is being concatenated)....

Longest Increasing Subsequence using Dynamic Programming:

Due to optimal substructure and overlapping subproblem property, we can also utilise Dynamic programming to solve the problem. Instead of memoization, we can use the nested loop to implement the recursive relation. The outer loop will run from i = 1 to N and the inner loop will run from j = 0 to i and use the recurrence relation to solve the problem....

Tags:
#Amazon #Binary Search #LIS #Samsung #Zoho #DSA #Dynamic Programming #Searching #Amazon #Samsung #Zoho #Binary Search #Dynamic Programming #Searching

Longest Increasing Sequence using Recursion:

Longest Increasing Subsequence using Dynamic Programming:

Contact Us

Categories
Learn the most popular programming languages in the world.