Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals @BackToBackSWE
Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals  @BackToBackSWE
Uploaded January 2019 | Updated November 2026, 3 hours ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πŸ“Ή Intuitive Video Explanations
πŸƒ Run Code As You Learn
πŸ’Ύ Save Progress
❓New Unseen Questions
πŸ”Ž Get All Solutions

Question: Given an array of all integers that may or may not be sorted, determine the length of the longest subsequence that is strictly non-decreasing.

What Is A Subsequence?

A subsequence of an array is a subset of the array that maintains temporal order.

It does not have to be contiguous but it might turn out to be contiguous by chance.


Problem Name / Variants

This problem also comes in the form of asking for the longest strictly decreasing subsequence.

This is longest non-decreasing subsequence meaning that we will have a non-strictly increasing subsequence (aka we can have deltas of 0 between contiguous elements in the subsequence).


Approach 1 (Brute Force)

We can enumerate all 2^n subsets of the original array and then test them for the non-decreasing property.

The answer will be the longest subset that has the property.

This is too expensive.


Approach 2 (Dynamic Programming)

Do you see the potential for a subproblem here?

If you do, then we have the opportunity to use dynamic programming.

Example
[ -1, 3, 4, 5, 2, 8 ]

At the index 0 I always know that I can have a subsequence of length 1.

In fact, at all positions the longest non-decreasing subsequence can be at least length 1.

We then look at index 1, I need to ask myself if the item at index 1 can lengthen the longest subseqence found at index 0.

We check if 3 is greater than or equal to 1...it is. Great. index 1 can be tacked on but...should I?

The LNDS (longest non-decreasing subsequence) at index 1 is 0.

The LNDS at index 0 is 1.

Yeah...it makes sense because if I tack 3 onto the LNDS I found for the subproblem of just [ -1 ] then at index 1 I will also have a LDNS.

So what we basically do is build a table and ask ourselves these questions all along the way.

EACH CELL REPRESENTS THE ANSWER TO THE SUBPROBLEM ASKED AGAINST the subsequence from index 0 to index i (including the element at index i).


Complexities:

Time: O( n^2 )

n is the length of the array.

For each of the n elements we will solve the LNDS problem which takes O(n) time, therefore we yield a O( n^2 ) runtime complexity.

Space: O( n )

We will store our answers for each of the n LNDS subproblems.


++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 17.12 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Find The Longest Increasing Subsequence - Dynamic Programming FundamentalsImplement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)Coding Interview | Binary Tree Traversal #shorts #datastructures #binarytree #codinginterviewBinary Tree Level Order Traversal - Drawing The Parallel Between Trees & GraphsFind the kth Largest or Smallest Element of an Array: From Sorting To Heaps To PartitioningInterval Scheduling Maximization (Proof w/ Exchange Argument)Coding Interview Concept | Asymptotic Behaviour #shorts #datastructures #codinginterviewEgg Dropping Problem: Dynamic Programming Fundamentals & Understanding Subproblem DecompositionImportant Coding Interview Concept | 3 Keys to Backtracking #shorts #datastructuresCoding Interview | Levels of a Binary Tree #shorts #datastructures #binarytree #codinginterviewGaurav Sen: Talking Daily Life At Uber & System Design Wisdom (The Back To Back Show - Show 1)The Change Making Problem - Fewest Coins To Make Change Dynamic Programming
Back To Back SWE |

Find The Longest Increasing Subsequence - Dynamic Programming Fundamentals

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER