✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-178

Longest Increasing Subsequence (LIS)

Explore how dynamic programming finds the longest subsequence whose elements appear in strictly increasing order.

Explanation

Overview

The Longest Increasing Subsequence problem finds the maximum-length subsequence of a sequence in which every selected element is greater than the element before it. The selected elements must preserve their original order but do not need to be adjacent.

Key concepts

Subsequence; Strictly increasing order; Predecessor states; Optimal substructure; Binary search optimization

Variables

A: The input array or sequence.; A[i]: The element at index i.; dp[i]: The length of the longest increasing subsequence ending at index i.; j: An earlier index considered as a possible predecessor.

Complexity

quadraticDynamicProgramming: O(n^2) time and O(n) space.; binarySearchOptimization: O(n log n) time and O(n) space.; variables: n is the number of elements in the input sequence.

Example

input: 10; 9; oneLongestIncreasingSubsequence: 2; 3; length: 4; explanation: The selected values are strictly increasing and preserve their original positions in the input.

Pseudocode

function LIS(A):
n = length(A)
if n == 0:
return 0
dp = array of size n filled with 1
answer = 1
for i = 0 to n - 1:
for j = 0 to i - 1:
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + 1)
answer = max(answer, dp[i])
return answer

Applications

Sequence analysis.; Trend detection.; Scheduling and ordering problems.; Computational biology.; Algorithmic pattern recognition.

Variables

A

The input array or sequence.

A[i]

The element at index i.

Dp[i]

The length of the longest increasing subsequence ending at index i.

J

An earlier index considered as a possible predecessor.

Example or application

Input

  • 10

  • 9

  • 2

  • 5

  • 3

  • 7

  • 101

  • 18

One Longest Increasing Subsequence

  • 2

  • 3

  • 7

  • 18

Length

4

Explanation

The selected values are strictly increasing and preserve their original positions in the input.

Definition

The Longest Increasing Subsequence problem finds the maximum-length subsequence of a sequence in which every selected element is greater than the element before it. The selected elements must preserve their original order but do not need to be adjacent.

Mathematical Representation

dp[i] = 1 + max(dp[j]) for all j < i where A[j] < A[i]; if no such j exists, dp[i] = 1.

Approaches

Quadratic Dynamic Programming

For each element, examines earlier elements to find the best increasing subsequence that can be extended.

Binary Search Optimization

Maintains a tails array and uses binary search to determine where each element belongs.

Reconstruction

Stores predecessor information to recover one actual longest increasing subsequence.

Pseudocode

function LIS(A):
n = length(A)
if n == 0:
return 0
dp = array of size n filled with 1
answer = 1
for i = 0 to n - 1:
for j = 0 to i - 1:
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + 1)
answer = max(answer, dp[i])
return answer

Complexity

Quadratic Dynamic Programming

O(n^2) time and O(n) space.

Binary Search Optimization

O(n log n) time and O(n) space.

Variables

n is the number of elements in the input sequence.

Key Concepts

  • Subsequence

  • Strictly increasing order

  • Predecessor states

  • Optimal substructure

  • Binary search optimization

Advantages

  • Identifies increasing patterns in a sequence.

  • The basic dynamic programming solution is easy to understand.

  • The optimized method handles large sequences more efficiently.

  • Can reconstruct an actual subsequence with additional tracking.

Limitations

  • The O(n^2) method becomes expensive for large arrays.

  • The optimized tails array does not necessarily represent the final LIS itself; it must be combined with predecessor tracking to reconstruct a sequence.

  • Strictly increasing and non-decreasing subsequences require different comparison rules.

Applications

  • Sequence analysis.

  • Trend detection.

  • Scheduling and ordering problems.

  • Computational biology.

  • Algorithmic pattern recognition.

Related Topics

  • Longest Common Subsequence

  • Binary Search

  • Dynamic Programming

  • Sequence Algorithms

Practice Question

Find the LIS length of [3, 1, 2, 5, 4].

Practice Answer

3. One LIS is [1, 2, 4] or [1, 2, 5].

Learning Objectives

  • Explain the central idea and purpose of longest increasing subsequence (lis).

  • Identify the assumptions, inputs, and conditions relevant to longest increasing subsequence (lis).

  • Evaluate an application of longest increasing subsequence (lis) for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures