LIS (Longest Increasing Subsequence)

Medium

Finds the longest subsequence where elements are in strictly increasing order.

📊 Complexity

Type	Value
Best	O(n²)
Average	O(n²)
Worst	O(n²)
Space	O(n)

🏷️ Tags

DPSubsequenceOptimization

📖 Introduction

LIS (Longest Increasing Subsequence) finds the longest subsequence where elements are in strictly increasing order while maintaining their relative positions. Elements don't need to be consecutive.

1/68

🎯Longest Increasing Subsequence

Find the longest subsequence where elements are in increasing order! • Array: [10, 22, 9, 33, 21, 50, 41, 60] "Increasing Subsequence"? • Keep order: Same order as original • Increasing: prev < next • Not consecutive: Can skip!

🔒

LIS (Longest Increasing Subsequence)

Medium

LIS (Longest Increasing Subsequence)

Finds the longest subsequence where elements are in strictly increasing order.

📊 Complexity

Type	Value
Best	O(n²)
Average	O(n²)
Worst	O(n²)
Space	O(n)

🏷️ Tags

DPSubsequenceOptimization

📖 Introduction

LIS (Longest Increasing Subsequence) finds the longest subsequence where elements are in strictly increasing order while maintaining their relative positions. Elements don't need to be consecutive.

1/68

🎯Longest Increasing Subsequence

🔒

🎯Longest Increasing Subsequence