> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/dynamic-programming/longest-ascending-subsequence-i-and-ii.md).

# 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

```java
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)&#x20;

**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.

![](https://1509805518-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MNkNlNl5fRVReS8KLNV%2F-Mk9om9Jubn73Y0YbK65%2F-Mk9pRP7hwoBTC3xYkb_%2Fimage.png?alt=media\&token=f1d3b25e-e8e4-487e-825b-76498bb267f6)

*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:

![](https://1509805518-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MNkNlNl5fRVReS8KLNV%2F-Mk9om9Jubn73Y0YbK65%2F-Mk9qtQxNDSQT2N-_oOy%2Fimage.png?alt=media\&token=9ad18976-53f0-43bc-a66b-99c180dac55c)

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