LeetCode Medium Challenge Day 15 | Longest Increasing Subsequence

PROBLEM LINK - CLICK

1. Initialization:

- An array lis is created to store the length of the LIS that ends at each index of the input array nums. Initially, all values in lis are set to 1, assuming each element is a subsequence of length 1 by itself.

2. Dynamic Programming Computation:

- We use a nested loop to update the lis array. For each element nums[i], we check all previous elements nums[j] (where j < i). If nums[i] is greater than nums[j], it means we can extend the subsequence ending at nums[j] by including nums[i]. We update lis[i] to be the maximum of its current value or lis[j] + 1.

3. Finding the Result:

- After filling the lis array, the maximum value in lis represents the length of the longest increasing subsequence in the input array.

CODE

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;  // Edge case: empty array

        int[] lis = new int[n];
        Arrays.fill(lis, 1);  // Initialize all LIS values to 1

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

        // Find the maximum value in lis array
        int max = lis[0];
        for (int i = 1; i < lis.length; i++) {
            if (lis[i] > max) {
                max = lis[i];
            }
        }

        return max;
    }
}