Longest Increasing Subsequence O(n log n) dynamic programming Java source code

Given an array of random numbers, find a longest increasing subsequence. This subsequence is not necessarily contiguous, or unique.

In this tutorial we illustrate a dynamic programming (DP) solution that runs in O(nlogn). Source code is available in Java. Two proofs are also presented. The first proof is done by induction. The second proof makes use of the fact that Patience Sort algorithm minimizes the number of piles, and since each pile contains cards in decreasing order, any increasing sequence can have at most one card from each pile.

This programming challenge is commonly given during technical/coding interviews at engineering firms such as Google and Microsoft.

Source code, implemented in Java:
https://bitbucket.org/StableSort/play/src/master/src/com/stablesort/challenge/LongestIncreasingSubsequence.java

Wikipedia: https://en.wikipedia.org/wiki/Longest_increasing_subsequence

"Patience Sort" is a general purpose sorting algorithm that in the process of sorting also finds a longest increasing subsequence. This video explains how the Patience Sort works by placing numbers (playing cards are used for illustration) into piles of decreasing values. If we also keep a pointer from the placed card to the top of the pile immediately on the left side, chains of pointers get created, leading to the left most pile. So at the end, you can pick any card on the right most pile and follow the pointers to the left most pile, recovering the (or one of the) longest increasing subsequence in reverse order.

Informal proof:
Since the cards within a pile form a decreasing sequence, any increasing sequence can use at most one card from each pile. So regardless of what strategy you use to play the game, the number of piles is always ≥ the length of any increasing sequence.
Since "Patience Sort" greedy strategy minimizes the number of piles and each pile is linked via pointers, following the pointers gives us a longest increasing sequence.

Proof by induction:
The first card, lets call it card-1, is put into pile-1 and obviously creates a subsequence of length 1. That’s our base case.

For the second step, assume that after placing the nth card, card-N, into a pile-K, a subsequence of length K is created. Lets see if this holds true for the next card, cardN+1. If cardN+1 is greater than card-N, it won’t be placed onto any pile to the left of pile-K since "Patience Sort" greedy strategy would have placed the previous card, card-N, into that pile instead of pile-K.

And it won’t be placed into pile-K since the rule for "Patience" game does not allow it.

Thus, cardN+1 is placed into some pile to the right, thereby, increasing the length of the previously calculated subsequence.

Finding the needed pile takes O(log n) time using binary search. This needs to be done for each card, so the overall running time is O(n log n).

leetcode 300 "Given an unsorted array of integers, find the length of longest increasing subsequence"
https://leetcode.com/problems/longest-increasing-subsequence/

Written and narrated by Andre Violentyev

Видео Longest Increasing Subsequence O(n log n) dynamic programming Java source code канала Stable Sort