Longest Increasing Subsequence - Java Solution

1. Introduction

This blog post explores the "Longest Increasing Subsequence" problem, a common challenge in dynamic programming. The problem focuses on finding the length of the longest subsequence in an array that is strictly increasing. This is an essential concept in computer science and mathematics, particularly in the areas of algorithm design and sequence analysis.

Problem

Given an integer array nums, the goal is to determine the length of the longest strictly increasing subsequence in the array.

Example scenarios:

1. For nums = [10,9,2,5,3,7,101,18], the longest increasing subsequence is [2,3,7,101] with a length of 4.

2. For nums = [0,1,0,3,2,3], the length is 4.

3. For nums = [7,7,7,7,7,7,7], the length is 1, as all elements are equal.

2. Solution Steps

1. Use dynamic programming to construct an array dp where dp[i] represents the length of the longest increasing subsequence ending with nums[i].

2. Initialize each element in dp to 1, as the minimum length for each element is 1.

3. Iterate through the array, for each element nums[i], compare it with previous elements nums[j] where j < i.

4. If nums[j] < nums[i], update dp[i] as Math.max(dp[i], dp[j] + 1).

5. Keep track of the maximum value in the dp array, which represents the length of the longest increasing subsequence.

6. Return the maximum value found.

3. Code Program

public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums)); // Test the function
    }

    // Function 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;
    }
}

Output:

4

Explanation:

1. lengthOfLIS: This function computes the length of the longest increasing subsequence in the array nums.

2. It initializes a dp array where dp[i] represents the longest increasing subsequence ending at nums[i].

3. The function iterates through each element of nums. For each element, it compares it with all previous elements to find the longest increasing subsequence ending at that element.

4. If a smaller element is found, dp[i] is updated to the maximum of its current value and the length of the increasing subsequence ending at the smaller element plus one.

5. The function keeps track of and updates the maximum length found so far.

6. This approach ensures that the problem is solved optimally at each step, building up the solution for the longest increasing subsequence.