concept · INFO-CS-ADS-178Longest 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
One Longest Increasing Subsequence
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.
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.
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