---
title: 'Longest Increasing Subsequence | Dynamic Programming Explained'
source: 'https://youtube.com/watch?v=646JqBD6Wxo'
video_id: '646JqBD6Wxo'
date: 2026-08-04
duration_sec: 72
---

# Longest Increasing Subsequence | Dynamic Programming Explained

> Source: [Longest Increasing Subsequence | Dynamic Programming Explained](https://youtube.com/watch?v=646JqBD6Wxo)

## Summary

This video explains how to solve the Longest Increasing Subsequence (LIS) problem using dynamic programming. It emphasizes that a subsequence does not require contiguous elements and demonstrates an efficient approach that reuses previously computed results rather than generating all subsequences.

### Key Points

- **Problem Definition** [00:02] — The task is to find the length of the longest increasing subsequence in an array, where elements do not need to be adjacent.
- **Example** [00:15] — For the array [2, 4, 6, 12], the answer is 4 because these numbers form an increasing subsequence.
- **Naive Approach** [00:29] — Generating all subsequences is exponential and inefficient.
- **DP Insight** [00:29] — For each number, consider the longest increasing subsequence that ends at that position. Every number is a subsequence of length 1 by itself.
- **Transition** [00:43] — For each position, look to the left: if the current number is larger than a previous number, it can extend that subsequence. Take the best valid subsequence before it and add one.
- **Dynamic Programming** [00:56] — Instead of generating all subsequences, reuse the best answer ending at each position. The maximum value built is the answer.

### Conclusion

The video demonstrates that dynamic programming provides an efficient solution to the LIS problem by reusing optimal subproblems, avoiding exponential time complexity.

## Transcript

You're given an array and asked to find the length of the longest increasing subsequence. Not sub array, but subsequence. So importantly, the numbers do not need to be next to each other. Take this example.
The answer here is four because 2 4 6 and 12 are increasing. Most people try to build all subsequences, but it gets exponentially worse. Instead, think like this. For every single number, check what
increasing subsequence can end here. We know that every number is at least a subsequence of length one by itself. Now look to the left. If the current number is bigger than a previous number, it can extend that subsequence. So for
each position, take the best valid subsequence before it and add one. Now watch what happens. At four, it can extend two. extend two. At six, it can extend two, four, or
So you pick the best one. That's dynamic programming. You're not generating everything. You're reusing the best answer ending at each position. And in the end, the biggest value you built is the answer. Like and follow for more DP
the answer. Like and follow for more DP problems.