# 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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/longest-ascending-subsequence-i-and-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.