Longest Increasing Subsequence

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

4

public class Solution {
    public Integer longest_increasing_subsequence(int[] nums) {
        // Your code goes here
    }
}

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.

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);
}

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.)

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);
}

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

Solution

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);
}