Longest Ascending Subsequence I & II
Given an array A[0]...A[n-1] of integers, find out the longest ascending subsequence.
Solution: Memoize longest subsequence at index, memoize previous step index of sequence
public class Solution {
public int[] longest(int[] a) {
if (a.length == 0) return new int[0];
int[] M = new int[a.length];
int[] prev = new int[a.length];
int maxIndex = 0;
for (int i = 0; i < a.length; i++){
M[i] = 1;
prev[i] = -1;
for (int j = 0; j < i; j++){
if (a[j] < a[i] && M[j] + 1 > M[i]){
M[i] = M[j] + 1;
prev[i] = j;
}
}
if (M[i] > M[maxIndex]) maxIndex = i;
}
return backTrack(a, prev, maxIndex, M[maxIndex]);
}
private int[] backTrack(int[] a, int[] prev, int maxIndex, int length){
int[] result = new int[length];
int index = length - 1;
while(maxIndex != -1){
result[index] = a[maxIndex];
maxIndex = prev[maxIndex];
index--;
}
return result;
}
}
TC: O(N^2)
SC: O(2N) = O(N) M and prev array
More insane solution: Patience Sort
High Level: Use piles of descending sequences to track length of longest sub-sequence.
Sorting rule: Solitaire style. Place current card in the left most pile, such that it forms a decreasing sequence with that pile.

Why is the number of piles the length of the longest subsequence?
Whenever a new card is placed, it can only form a new pile if every pile to its left ends in a number smaller than the new card.
example:

Since the bottom card of each pile forms an increasing array, we can binary search the placement of each new card.
TC: NLogN
SC: N
Last updated
Was this helpful?