Longest Increasing Subsequence (LIS)

Definition

Definition

The Longest Increasing Subsequence (LIS) algorithm is a dynamic programming approach used to find the longest subsequence in an array where the elements are in increasing order

Explanation

The LIS algorithm works by iterating through each element in the given array and maintaining a separate array to store the length of the longest increasing subsequence ending at each index. At each step, the algorithm compares the current element with all previous elements to find the longest increasing subsequence ending at the current element. It updates the length of the longest increasing subsequence for the current element based on the maximum length found so far. Finally, the algorithm returns the maximum length of the longest increasing subsequence

Guidance

• Initialize an array dp of size equal to the length of the input array, where dp[i] will store the length of the longest increasing subsequence ending at index i
• Set all elements of dp to 1 initially, as the minimum length of any subsequence is 1 (which is the element itself)
• Iterate through each element arr[i] in the input array
• For each element, iterate through all previous elements arr[j] where j < i
• If arr[j] < arr[i], meaning the current element can be part of the increasing subsequence ending at index i, update dp[i] to max(dp[i], dp[j] + 1)
• After iterating through all previous elements, dp[i] will hold the length of the longest increasing subsequence ending at index i
• Find the maximum value in the dp array, which represents the length of the longest increasing subsequence
• This maximum value is the result

Tips

• utilize dynamic programming to efficiently solve the problem by breaking it down into smaller subproblems
• optimize the algorithm by using binary search to reduce the time complexity
• pay attention to the indices while updating the dp array to correctly compute the length of the longest increasing subsequence ending at each index

Practice

Practice

lis(arr):
  # Initialize an array dp to store lengths of longest increasing subsequences
  dp = array of length equal to size of arr, initialized with 1s
  for i from 0 to length of arr - 1:
    for j from 0 to i - 1:
      if arr[j] < arr[i]:
        # Update the length of longest increasing subsequence ending at index i
        dp[i] = max(dp[i], dp[j] + 1)
  # Find the maximum value in dp
  max_length = maximum value in dp
  return max_length

Solution

package main

func lengthOfLIS(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    dp := make([]int, n)
    dp[0] = 1
    maxLen := 1
    for i := 1; i < n; i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && dp[i] < dp[j]+1 {
                dp[i] = dp[j] + 1
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
        }
    }
    return maxLen
}

public class LongestIncreasingSubsequence {

  public static int lengthOfLIS(int[] nums) {
    int n = nums.length;
    if (n == 0) {
      return 0;
    }
    int[] dp = new int[n];
    dp[0] = 1;
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
          dp[i] = dp[j] + 1;
        }
      }
      if (dp[i] > maxLen) {
        maxLen = dp[i];
      }
    }
    return maxLen;
  }
}

function lengthOfLIS(nums) {
  const n = nums.length;
  if (n === 0) {
    return 0;
  }
  const dp = new Array(n).fill(1);
  let maxLen = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
      }
    }
    if (dp[i] > maxLen) {
      maxLen = dp[i];
    }
  }
  return maxLen;
}

fun lengthOfLIS(nums: IntArray): Int {
    val n = nums.size
    if (n == 0) return 0
    val dp = IntArray(n) { 1 }
    var maxLen = 1
    for (i in 1 until n) {
        for (j in 0 until i) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i]
        }
    }
    return maxLen
}

def lengthOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0
    dp = [1] * n
    maxLen = 1
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
        if dp[i] > maxLen:
            maxLen = dp[i]
    return maxLen

fn length_of_lis(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    if n == 0 {
        return 0;
    }
    let mut dp = vec![1; n];
    let mut max_len = 1;
    for i in 1..n {
        for j in 0..i {
            if nums[i] > nums[j] && dp[i] < dp[j] + 1 {
                dp[i] = dp[j] + 1;
            }
        }
        if dp[i] > max_len {
            max_len = dp[i];
        }
    }
    max_len
}

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  if (n === 0) return 0;
  const dp: number[] = new Array(n).fill(1);
  let maxLen = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
      }
    }
    if (dp[i] > maxLen) {
      maxLen = dp[i];
    }
  }
  return maxLen;
}