Longest Increasing Subsequence (LIS) Editorial

Practice Problem Link: Longest Increasing Subsequence | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A, find the length of the longest strictly increasing subsequence.

Naive Approach

We can solve this problem by a brute force recursion. Let LIS(i) denote the length of the LIS ending at index i. Then, 

1. LIS(i) = 1 + max(LIS(j)) where 0 < j < i and arr[i] > arr[j].
2. LIS(i) = 1, if no such j exists.

Our answer will maximum value of LIS(i), overall i from 1 to n.

Analysis

• Time Complexity: Exponential
• Space Complexity: O(1)

Implementation

C++

int result;
int getLIS(vector<int> &A, int n) {
   if(n == 1) {
       return 1;
   }
   int answer, endingPoint = 1;
   for(int i = 1; i < n; i++) {
       answer = getLIS(A, i);
       if(A[n - 1] > A[i - 1] && answer > endingPoint - 1) {
           endingPoint = answer + 1;
       }
   }
   result = max(result, endingPoint);
   return endingPoint;
}
int getLengthOfLIS(vector<int> A) {
   int n = A.size();
   result = 1;
   getLIS(A, n);
   return result;
}

Java

class Solution {
   int result;
   int getLIS(int A[], int n) {
       if(n == 1) {
           return 1;
       }
       int answer, endingPoint = 1;
       for(int i = 1; i < n; i++) {
           answer = getLIS(A, i);
           if(A[n - 1] > A[i - 1] && answer > endingPoint - 1) {
               endingPoint = answer + 1;
           }
       }
       result = Math.max(result, endingPoint);
       return endingPoint;
   }
   int getLengthOfLIS(int[] A) {
       int n = A.length;
       result = 1;
       getLIS(A, n);
       return result;
   }
}

Optimal Approach

Observe that in the above naive approach, there are many repeated recursive calls with the same parameters, in the getLIS() function. So, we can memoize those repeated calls with Dynamic Programming. Let DP[i] represent the length of the LIS ending at index i, as the states of the DP.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Implementation

C++

int result;
vector<int> dp;
int getLIS(vector<int> &A, int n) {
   if(n == 1) {
       return 1;
   }
   int answer, endingPoint = 1;
   for(int i = 1; i < n; i++) {
       if(dp[i] != -1) {
           answer = dp[i];
       } else {
           answer = getLIS(A, i);
           dp[i] = answer;
       }
       if(A[n - 1] > A[i - 1] && answer > endingPoint - 1) {
           endingPoint = answer + 1;
       }
   }
   result = max(result, endingPoint);
   return endingPoint;
}
int getLengthOfLIS(vector<int> A) {
   int n = A.size();
   dp.assign(n + 1, -1);
   result = 1;
   getLIS(A, n);
   return result;
}

Java

class Solution {
   int result;
   int dp[];
   int getLIS(int A[], int n) {
       if(n == 1) {
           return 1;
       }
       int answer, endingPoint = 1;
       for(int i = 1; i < n; i++) {
           if(dp[i] != -1) {
               answer = dp[i];
           } else {
               answer = getLIS(A, i);
               dp[i] = answer;
           }
           if(A[n - 1] > A[i - 1] && answer > endingPoint - 1) {
               endingPoint = answer + 1;
           }
       }
       result = Math.max(result, endingPoint);
       return endingPoint;
   }
   int getLengthOfLIS(int[] A) {
       int n = A.length;
       dp = new int[n + 1];
       Arrays.fill(dp, -1);
       result = 1;
       getLIS(A, n);
       return result;
   }
}

Implementation (Bottom-up)

C++

int getLengthOfLIS(vector<int> A) {
   int n = A.size();
   vector<int> dp(n + 1, INT_MAX);
   dp[0] = INT_MIN;
   for(int i = 0; i < n; i++) {
       for(int j = 1; j <= n; j++) {
           if(dp[j - 1] < A[i] && A[i] < dp[j]) {
               dp[j] = A[i];
           }
       }
   }
   int result = 0, counter = 0;
   for(int x: dp) {
       if(x != INT_MAX) {
           result = counter;
       }
       counter++;
   }
   return result;
}

Java

class Solution {
   int getLengthOfLIS(int[] A) {
       int n = A.length;
       int[] dp = new int[n + 1];
       Arrays.fill(dp, Integer.MAX_VALUE);
       dp[0] = Integer.MIN_VALUE;
       for(int i = 0; i < n; i++) {
           for(int j = 1; j <= n; j++) {
               if(dp[j - 1] < A[i] && A[i] < dp[j]) {
                   dp[j] = A[i];
               }
           }
       }
       int result = 0;
       for(int i = 0; i <= n; i++) {
           if(dp[i] != Integer.MAX_VALUE) {
               result = i;
           }
       }
       return result;
   }
}