#0278

Longest Increasing Subsequence

MediumDSA28 min20 XP

Problem

Given nums, return the length of the longest strictly increasing subsequence. A subsequence keeps order but may skip elements.

Why This Matters

LIS is a must-know DP problem, and the patience-sorting version shows how binary search optimizes state.

Function Signature

def length_of_lis(nums):

Examples

Example 1

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

Output4

One LIS is [2, 3, 7, 18].

Constraints

Return the exact requested value.
Handle edge cases cleanly.
Use the intended DSA pattern when brute force would scale poorly.

CodePython

def length_of_lis(nums):
    """
    Input example: nums = [10,9,2,5,3,7,101,18]
    Return: 4
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

def length_of_lis(nums):
    """
    Input example: nums = [10,9,2,5,3,7,101,18]
    Return: 4
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Classic LIS

Input[10,9,2,5,3,7,101,18]

Expected4

The best increasing subsequence has length four.

Duplicates are not increasing

Input[2,2,2]

Expected1

Strictly increasing means equal values cannot extend the subsequence.

Hidden Test Categories

empty inputalready increasingstrictly decreasing