Longest Increasing Subsequence

Problem

Given an integer array nums, write a function that returns the length of the longest increasing subsequence within the array. The subsequence does not have to be contiguous, but the elements must be strictly increasing (i.e. nums[i] < nums[j] for all i < j).

Input:

nums = [8,2,4,3,6,12]

Output:

Explanation: The longest increasing subsequence is [2,4,6,12], which has a length of 4.

Explanation

This solution uses bottom-up dynamic programming to solve the problem. We create an integer array dp of length n where n is the length of the input array nums. dp[i] is equal to length of the longest increasing subsequence ending at the i-th index of nums. Since a single element is an increasing subsequence of length 1, we initialize dp with 1 for all elements.

def longest_increasing_subsequence(nums):
  if not nums:
    return 0

  n = len(nums)
  dp = [1] * n

  for i in range(1, n):
    for j in range(i):
      if nums[i] > nums[j]:
        dp[i] = max(dp[i], dp[j] + 1)

  return max(dp)

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Arrays.stream(dp).max().orElse(0);
}

func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }

    result := 0
    for _, val := range dp {
        result = max(result, val)
    }
    return result
}

function longestIncreasingSubsequence(nums: number[]): number {
  if (!nums || nums.length === 0) {
    return 0;
  }

  let n: number = nums.length;
  let dp: number[] = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

We then use a for-loop i to iterate over each index in the array. The body of the loop determines the correct value for dp[i].

Inside the body of the loop, we use another for-loop j to iterate over all indexes before i. If nums[i] > nums[j], we update dp[i] to be the maximum of dp[i] and dp[j] + 1. This is because the i-th element can extend the increasing subsequence ending at the j-th element by 1. (If dp[i] is already greater than dp[j] + 1, we leave it as is - a longer subsequence ending at i has already been found.)

Finally, we return the maximum value in dp as the length of the longest increasing subsequence.

Problem

Explanation

Solution