DP / Transition TypeLinear DPMedium

Linear DP — Longest Increasing Subsequence

For each element, check all previous elements. If arr[j] < arr[i], dp[i] = max(dp[i], dp[j]+1). O(N²).

LC
Practice on LeetCode 300: Longest Increasing Subsequence
Open Problem

Linear DP Pattern

In linear DP, each state dp[i] depends on previous states dp[0..i-1]. The transition scans backward linearly. LIS: dp[i] = length of longest increasing subsequence ending at index i.

Recurrence

dp[i] = 1 // base: element alone
for j = 0 to i-1:
  if arr[j] < arr[i]:
    dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp[0..n-1])
Interactive Visualization
Current i
Comparing j
Computed
In LIS
Array + dp values
Step 0 of 0
i
—
j
—
dp[i]
—
LIS Length
0
Ready. Press Play or Next to start.
✓ Done
Speed
C++ — LIS O(N²)
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);

    return *max_element(dp.begin(), dp.end());
}
Complexity
Time
O(N²)

Nested loops. O(N log N) with patience sorting.

Space
O(N)

DP array of size N.

📝 Notes

▼