D
DevExCode

LeetCode 2407: Longest Increasing Subsequence II Solution

Master LeetCode problem 2407 (Longest Increasing Subsequence II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming to find the longest increasing subsequence with a maximum difference of k between adjacent elements. The idea is to maintain a list of the longest increasing subsequences ending at each index of the input array. For each index, we can iterate through all previous elements to find the longest increasing subsequence that ends with that element and also satisfies the maximum difference constraint.

Algorithm:

  1. Initialize a dynamic programming array dp of length equal to the input array nums.
  2. For each index i in the array nums, iterate from index j=0 to i-1:
    • If nums[i] - nums[j] <= k, update dp[i] to the maximum of dp[i] and dp[j] + 1.
  3. Find the maximum value in the dp array which represents the length of the longest increasing subsequence that satisfies the maximum difference constraint.
  4. Return the maximum value as the result.

Time Complexity:

The time complexity of this approach is O(n^2), where n is the length of the input array nums.

Space Complexity:

The space complexity is O(n) to store the dynamic programming array.

:

Solution Code

class Solution {
    public int lengthOfLIS(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLen = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] - nums[j] <= k) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        return maxLen;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2407 (Longest Increasing Subsequence II)?

This page provides optimized solutions for LeetCode problem 2407 (Longest Increasing Subsequence II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2407 (Longest Increasing Subsequence II)?

The time complexity for LeetCode 2407 (Longest Increasing Subsequence II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2407 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2407 in Java, C++, or Python.

Back to LeetCode Solutions