Longest Increasing Subsequence II

• 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.

1class Solution {2    public int lengthOfLIS(int[] nums, int k) {3        int n = nums.length;4        if (n == 0) {5            return 0;6        }7        int[] dp = new int[n];8        java.util.Arrays.fill(dp, 1);9        int maxLength = 1;10        for (int i = 0; i < n; i++) {11            for (int j = 0; j < i; j++) {12                if (nums[i] > nums[j] && nums[i] - nums[j] <= k) {13                    dp[i] = Math.max(dp[i], 1 + dp[j]);14                }15            }16            maxLength = Math.max(maxLength, dp[i]);17        }18        return maxLength;19    }20}

• Determine the maximum possible value maxVal in nums to set the range for our data structure.
• Initialize a Segment Tree data structure that can perform range maximum queries and point updates over the values [1, maxVal]. All lengths in the tree are initialized to 0.
• Initialize a variable ans to 0 to track the maximum length found so far.
• Iterate through each number num in the input array nums.
• For each num, determine the query range for valid preceding values: [max(1, num - k), num - 1].
• Query the Segment Tree for the maximum length within this range. Let this be prevMaxLen.
• The length of the longest subsequence ending with the current num is currentLen = 1 + prevMaxLen.
• Update the Segment Tree at index num with this new currentLen.
• Update the overall answer: ans = max(ans, currentLen).
• After iterating through all numbers, ans will be the final result.

The O(n^2) DP approach is slow because for each element, we linearly scan all previous elements. We can optimize this search. The condition nums[i] > nums[j] and nums[i] - nums[j] <= k is equivalent to finding a j < i such that nums[j] is in the range [nums[i] - k, nums[i] - 1].

This suggests a DP state based on values rather than indices. Let lengths[v] be the length of the longest valid subsequence ending with value v. When processing a number num from the input, we need to find 1 + max(lengths[v]) for all v in [num - k, num - 1]. This is a range maximum query.

A Segment Tree is an ideal data structure for this. It can perform range maximum queries and point updates in logarithmic time. We build a segment tree over the range of possible values in nums (e.g., [1, 10^5]).

For each num in nums, we query the segment tree for the maximum length in the range [max(1, num - k), num - 1]. Let the result be L. The new length for a subsequence ending in num is L + 1. We then update the segment tree at position num with this new length. The overall maximum length found during this process is the answer.

1class Solution {2    // Segment Tree array3    int[] tree;4    // The size of the value range the tree covers5    int valueRange;6 7    // Helper to build/initialize the tree8    private void build(int size) {9        valueRange = size;10        tree = new int[4 * valueRange];11    }12 13    // Helper to update a value at a specific index (value)14    private void update(int node, int start, int end, int idx, int val) {15        if (start == end) {16            tree[node] = val;17            return;18        }19        int mid = start + (end - start) / 2;20        if (start <= idx && idx <= mid) {21            update(2 * node, start, mid, idx, val);22        } else {23            update(2 * node + 1, mid + 1, end, idx, val);24        }25        tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);26    }27 28    // Helper to query for the maximum value in a given range [l, r]29    private int query(int node, int start, int end, int l, int r) {30        if (r < start || end < l || l > r) {31            return 0; // Return 0 for no overlap or invalid range32        }33        if (l <= start && end <= r) {34            return tree[node];35        }36        int mid = start + (end - start) / 2;37        int p1 = query(2 * node, start, mid, l, r);38        int p2 = query(2 * node + 1, mid + 1, end, l, r);39        return Math.max(p1, p2);40    }41 42    public int lengthOfLIS(int[] nums, int k) {43        int maxVal = 0;44        for (int num : nums) {45            maxVal = Math.max(maxVal, num);46        }47 48        build(maxVal);49        int ans = 0;50 51        for (int num : nums) {52            int startRange = Math.max(1, num - k);53            int endRange = num - 1;54 55            int prevMaxLen = query(1, 1, valueRange, startRange, endRange);56            int currentLen = prevMaxLen + 1;57 58            update(1, 1, valueRange, num, currentLen);59            ans = Math.max(ans, currentLen);60        }61        return ans;62    }63}