Longest Increasing Subsequence - Java Solution

1. Introduction

In this blog post, we will explore a classic problem in dynamic programming - finding the Longest Increasing Subsequence (LIS) in an array of integers. The LIS is a subsequence of a given sequence in which the elements are in sorted order, lowest to highest, and in which the sequence is as long as possible.

Problem

Given an array of integers A, find the length of the longest strictly increasing subsequence of A. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

2. Solution Steps

1. Initialize an array dp of the same length as A, where each element is 1. dp[i] represents the length of the longest increasing subsequence ending with A[i].

2. Iterate over the array A starting from the second element.

3. For each element A[i], iterate over all previous elements A[j] where j < i.

4. If A[j] < A[i], update dp[i] to be the maximum of dp[i] and dp[j] + 1.

5. The length of the longest increasing subsequence will be the maximum value in dp.

6. Return the maximum value in dp.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of LIS: " + lengthOfLIS(nums1));

        int[] nums2 = {0, 1, 0, 3, 2, 3};
        System.out.println("Length of LIS: " + lengthOfLIS(nums2));

        int[] nums3 = {7, 7, 7, 7, 7, 7, 7};
        System.out.println("Length of LIS: " + lengthOfLIS(nums3));
    }

    // Method to find the length of the longest increasing subsequence
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

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

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

        return maxLen; // The length of the longest increasing subsequence
    }
}

Output:

Length of LIS: 4
Length of LIS: 4
Length of LIS: 1

Explanation:

For the first example, the longest increasing subsequence is [2,3,7,101], so the length is 4. The method lengthOfLIS uses dynamic programming to build up a solution. It iterates through each element and calculates the length of the longest increasing subsequence ending at that element. The final answer is the maximum length found in the array.