300. Longest Increasing Subsequence

← All Problems
medium Dynamic Programming
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of [0,3,1,6,2,2,7].

Example

nums = [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4

One longest increasing subsequence is [2, 3, 7, 101]. Another is [2, 5, 7, 101] or [2, 3, 7, 18]. All have length 4, and no strictly increasing subsequence of length 5 exists.

dp[i] represents the length of the longest increasing subsequence ending at index i. For each element, look back at all previous elements — if nums[j] < nums[i], then you can extend that subsequence by one: dp[i] = max(dp[i], dp[j] + 1). The answer is the maximum value in dp.

Why this works

For each element, you ask: “What is the longest increasing subsequence I can build that ends right here?” You check every previous element – if it is smaller, you could append the current element to that subsequence. Taking the maximum across all such extensions gives the best answer at each position.

Step by step

  1. Initialize dp — every element forms a subsequence of length 1 on its own, so fill dp with 1s.
  2. For each element i — look at all earlier elements j (from 0 to i-1).
  3. Check if extendable — if nums[j] < nums[i], the current element can continue that increasing subsequence, so dp[i] = max(dp[i], dp[j] + 1).
  4. Return the global max — the answer is the largest value in the dp array.
Time: O(n²) Space: O(n) 
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // every element is a subsequence of length 1 by itself
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) { // nums[i] can extend the subsequence ending at j
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1); // every element is a subsequence of length 1 by itself
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) { // nums[i] can extend the subsequence ending at j
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n  # every element is a subsequence of length 1 by itself
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:  # nums[i] can extend the subsequence ending at j
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)