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