Longest Increasing Subsequence II

This approach uses a straightforward dynamic programming solution. We define dp[i] as the length of the longest valid subsequence ending at index i. To compute dp[i], we iterate through all previous elements nums[j] (where j < i) and check if they can form a valid pair with nums[i]. If they can, we update dp[i] based on dp[j].

• Initialize an array dp of size n (the length of nums) with all elements set to 1. dp[i] will store the length of the longest valid subsequence ending at index i.
• Initialize a variable maxLength to 1, which will store the final answer.
• Iterate through the nums array with an index i from 1 to n-1.
• For each i, iterate through all previous indices j from 0 to i-1.
• Inside the inner loop, check if nums[j] can precede nums[i] in a valid subsequence. The conditions are:
  1. nums[i] > nums[j] (strictly increasing).
  2. nums[i] - nums[j] <= k (difference at most k).
• If both conditions are met, it means we can extend the subsequence ending at j with nums[i]. Update dp[i] to the maximum of its current value and 1 + dp[j].
• After the inner loop finishes for a given i, update maxLength = max(maxLength, dp[i]).
• After the outer loop completes, maxLength will hold the length of the longest valid subsequence. Return maxLength.

This method is a direct application of dynamic programming for subsequence problems. We build up the solution by finding the longest subsequence ending at each position in the input array.

Let dp[i] be the length of the longest increasing subsequence that satisfies the condition and ends with the element nums[i]. To calculate dp[i], we look at all previous elements nums[j] where j < i. If nums[j] is smaller than nums[i] and their difference is at most k, then nums[i] can extend the subsequence ending at nums[j]. Therefore, we can update dp[i] with 1 + dp[j]. We take the maximum over all such valid j's.

The base case is dp[i] = 1 for all i, as any single element is a valid subsequence of length 1. The final answer is the maximum value in the dp array after it has been fully computed.

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