O(N²) DP

int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++)
  for (int j = 0; j < i; j++)
    if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
return Arrays.stream(dp).max().getAsInt();
Advertisement

Patience sort O(N log N)

List piles = new ArrayList<>();
for (int x : arr) {
  int idx = Collections.binarySearch(piles, x);
  if (idx < 0) idx = -idx - 1;
  if (idx == piles.size()) piles.add(x);
  else piles.set(idx, x);
}
return piles.size();
Advertisement

Why patience works

Maintain increasing 'top of pile'. Binary-search insert position. Size = LIS length. Loses actual subsequence but keeps length.

O(N²) DP

int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++)
  for (int j = 0; j < i; j++)
    if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
return Arrays.stream(dp).max().getAsInt();

Patience sort O(N log N)

List piles = new ArrayList<>();
for (int x : arr) {
  int idx = Collections.binarySearch(piles, x);
  if (idx < 0) idx = -idx - 1;
  if (idx == piles.size()) piles.add(x);
  else piles.set(idx, x);
}
return piles.size();

Why patience works

Maintain increasing 'top of pile'. Binary-search insert position. Size = LIS length. Loses actual subsequence but keeps length.

Reconstructing the LIS

With DP approach, track predecessors. Walk back from max cell.