Pseudo-code:

text
Initialize dp array of size N with 1s
max_len = 1
For i from 0 to N-1:
    For j from 0 to i-1:
        If nums[j] < nums[i] AND nums[i] - nums[j] <= k:
            dp[i] = max(dp[i], dp[j] + 1)
    max_len = max(max_len, dp[i])
Return max_len

Time Complexity: $O(N^2)$ Why it fails: The constraints state that nums.length can be up to $10^5$. An $O(N^2)$ solution would perform approximately $10^{10}$ operations, which far exceeds the typical limit of $10^8$ operations per second allowed by online judges. This results in a Time Limit Exceeded (TLE) error.

Core Insight for Longest Increasing Subsequence II

The brute force failure stems from the inner loop, which searches for the optimal previous state j linearly. We need to optimize this search.

Let's reframe the DP state. Instead of dp[i] being the LIS ending at index i, let dp[val] be the length of the longest valid subsequence ending with the value val.

When we process a number x from the input array nums, we want to extend a subsequence ending with a value v such that:

1. v < x (Strictly increasing)
2. x - v <= k (Difference constraint)

Rearranging these inequalities, we are looking for a value v in the range [x - k, x - 1]. Specifically, we want to find the maximum dp[v] where v falls in that range.

The transition becomes: $dp[x] = 1 + \max(dp[v]) \quad \text{for all } v \in [\max(1, x-k), x-1]$

The core insight is that finding the maximum value in a contiguous range [L, R] and updating a value at a specific index are operations efficiently supported by a Segment Tree (or a Fenwick Tree/Binary Indexed Tree).

Visual Description: Imagine the range of possible values (1 to 100,000) as a fixed-size array managed by a Segment Tree. Initially, all values are 0. As we iterate through nums, for a number x, we query the Segment Tree for the maximum value in the window [x-k, x-1]. This query returns the length of the longest valid prefix. We add 1 to this length and update the position x in the Segment Tree with this new maximum. The Segment Tree allows both the query and the update to happen in logarithmic time relative to the maximum possible value.

Execution Flow

1. Initialization:

   • Identify the maximum possible value M (based on constraints, $10^5$).
   • Initialize a Segment Tree covering the range [0, M].
   • Initialize global_max = 1.

2. Iteration:

   • Loop through each integer num in the input array nums.
   • Step 2a (Define Range): Calculate the lower bound for the query. Since the difference must be at most k, the smallest valid predecessor is num - k. Since the sequence is strictly increasing, the largest valid predecessor is num - 1. The query range is [max(0, num - k), num - 1].
   • Step 2b (Query): Perform tree.query(lower_bound, num - 1). Let the result be max_prev_len.
   • Step 2c (Calculate): The length of the subsequence ending at num is current_len = max_prev_len + 1.
   • Step 2d (Update): Perform tree.update(num, current_len). Note: If the tree already has a larger value at num (from an earlier occurrence of the same number), we typically take the max, but since we process left-to-right and strictly increasing requires different indices, simply updating or maximizing works. In this context, maximizing is safer: update(num, current_len).
   • Step 2e (Track Max): Update global_max = max(global_max, current_len).

3. Termination:

   • Return global_max (or the result of tree.query(0, M)).

Proof of Correctness

The correctness relies on the invariant of the Longest Increasing Subsequence DP.

• Invariant: At any point in the iteration, the value stored at index v in the Segment Tree represents the length of the longest valid subsequence found so far that ends with the value v.
• Transition: When processing num, any valid predecessor prev must satisfy num - k <= prev < num. Querying the range [num - k, num - 1] retrieves exactly $\max(dp[prev])$ for all valid predecessors processed so far.
• Ordering: By iterating through nums from left to right, we ensure that we only consider subsequences ending at indices $j < i$, preserving the original array order requirement.

Therefore, the algorithm correctly implements the recurrence relation $dp[i] = 1 + \max(dp[j])$ efficiently.

Reference Implementation

C++ Solution for LeetCode 2407

cpp
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class SegmentTree {
private:
    int n;
    vector<int> tree;

public:
    SegmentTree(int size) {
        n = size;
        tree.resize(2 * n, 0);
    }

    // Update value at position p to be max(current, value)
    void update(int p, int value) {
        p += n; // Move to leaf
        tree[p] = value; 
        for (; p > 1; p >>= 1) {
            tree[p >> 1] = max(tree[p], tree[p ^ 1]);
        }
    }

    // Query max in range [l, r)
    int query(int l, int r) {
        int res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++]);
            if (r & 1) res = max(res, tree[--r]);
        }
        return res;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        int max_val = 0;
        for (int x : nums) max_val = max(max_val, x);
        
        // Segment tree size covers 0 to max_val
        SegmentTree segTree(max_val + 1);
        int global_max = 1;

        for (int num : nums) {
            // We want max value in range [num - k, num - 1]
            // Lower bound must be at least 0 (or 1 depending on constraints, here values >= 1)
            int left = max(0, num - k);
            int right = num; // query is [left, right) which means indices up to num-1
            
            int max_prev_len = segTree.query(left, right);
            int current_len = max_prev_len + 1;
            
            // Update the tree at position 'num'
            // We need to ensure we don't overwrite a larger value if one exists
            // (though standard LIS logic usually implies strictly larger extensions)
            // However, strictly speaking, we update position `num` with the new best length.
            segTree.update(num, current_len);
            
            global_max = max(global_max, current_len);
        }
        
        return global_max;
    }
};

Java Solution for LeetCode 2407

java
class Solution {
    // Standard iterative Segment Tree for Range Maximum Query
    static class SegmentTree {
        int n;
        int[] tree;

        public SegmentTree(int size) {
            n = size;
            tree = new int[2 * n];
        }

        public void update(int index, int value) {
            index += n;
            tree[index] = value;
            while (index > 1) {
                tree[index >> 1] = Math.max(tree[index], tree[index ^ 1]);
                index >>= 1;
            }
        }

        public int query(int left, int right) {
            int res = 0;
            left += n;
            right += n;
            while (left < right) {
                if ((left & 1) == 1) {
                    res = Math.max(res, tree[left++]);
                }
                if ((right & 1) == 1) {
                    res = Math.max(res, tree[--right]);
                }
                left >>= 1;
                right >>= 1;
            }
            return res;
        }
    }

    public int lengthOfLIS(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        SegmentTree st = new SegmentTree(maxVal + 1);
        int globalMax = 0;

        for (int num : nums) {
            // Range [num - k, num - 1]
            // In the query implementation, right is exclusive, so we pass 'num'
            int left = Math.max(0, num - k);
            int right = num;
            
            int maxPrev = st.query(left, right);
            int currentLen = maxPrev + 1;
            
            st.update(num, currentLen);
            globalMax = Math.max(globalMax, currentLen);
        }

        return globalMax;
    }
}

Python Solution for LeetCode 2407

python
class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        max_val = max(nums)
        # Segment Tree array size. 2 * size is sufficient for iterative implementation
        n = max_val + 1
        tree = [0] * (2 * n)

        def update(index, value):
            index += n
            tree[index] = value
            while index > 1:
                tree[index >> 1] = max(tree[index], tree[index ^ 1])
                index >>= 1

        def query(left, right):
            # Query range [left, right)
            res = 0
            left += n
            right += n
            while left < right:
                if left & 1:
                    res = max(res, tree[left])
                    left += 1
                if right & 1:
                    right -= 1
                    res = max(res, tree[right])
                left >>= 1
                right >>= 1
            return res

        global_max = 0
        for num in nums:
            # We look for the best previous length in range [num - k, num - 1]
            left = max(0, num - k)
            right = num # Exclusive upper bound
            
            max_prev = query(left, right)
            current_len = max_prev + 1
            
            update(num, current_len)
            global_max = max(global_max, current_len)
            
        return global_max