Longest Increasing Subsequence

Problem Statement

Given an unsorted array of integers, find the length of the longest increasing subsequence (LIS). An increasing subsequence is a sequence of elements where each element is strictly greater than the previous one, but they don't need to be adjacent in the original array.

Solution Approach

We'll use dynamic programming to solve this efficiently. We'll create an array where each element represents the length of the LIS ending at that index. We'll build this array by comparing each element with all previous elements, updating the LIS length when we find a smaller element that can be part of the increasing subsequence.

Interactive Visualization

Input Sequence:

Index	0	1	2	3	4	5	6	7	8
Value	10	22	9	33	21	50	41	60	80
LIS Length

Step: 0 of 9

Explanation:

Final Result

The length of the Longest Increasing Subsequence is: -Infinity