LeetCode 300 - Longest Increasing Subsequence

This Medium problem asks for the length of the longest strictly increasing subsequence. The selected values do not have to be contiguous, but they must preserve their order in the input. I used dynamic programming to record the best subsequence ending at each index.

---

Problem link and explanation

• Problem: 300. Longest Increasing Subsequence
• Summary: Given an integer array, return the maximum length of a subsequence whose values are strictly increasing.

Every element can form a subsequence of length one by itself, so the DP array starts with ones. For each position, the solution checks earlier elements that can precede the current value.

---

Approach

I defined dp[i] as the length of the longest increasing subsequence ending at index i. If j < i and nums[j] < nums[i], the current value can extend the subsequence ending at j.

for i in range(1, n):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)

The longest subsequence does not have to end at the final array position, so the answer is max(dp) rather than dp[-1].

For an input such as [10, 9, 2, 5, 3, 7], the state for 7 considers the earlier 2, 5, and 3. Both 2 → 5 → 7 and 2 → 3 → 7 are valid. The transition selects the longest compatible previous state and adds the current element.

---

Complexity analysis

• Time complexity: O(n²)
  • Every index compares itself with all earlier indices.
• Space complexity: O(n)
  • The DP array stores one length per input position.

An O(n log n) solution is possible with binary search, but this implementation stays with the quadratic DP because its state and transition directly express which earlier subsequence the current value extends.

---

Implementation code

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n

        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

---

Summary and reflection

Defining the state as the best answer ending at a specific position made the transition concrete. The current element only connects to a smaller earlier value, and the solution chooses the longest state among those valid predecessors. The two details worth keeping are that a subsequence is not a contiguous range and that the final answer may appear anywhere in the DP array.