AlgoFlow — Algorithms, Visualized

Dynamic Programming/Longest Increasing Subsequence

subsequencepatience-sortordering

Press play to start

1int lis(int arr[], int n) {
  int dp[n];
  for (int k = 0; k < n; k++) dp[k] = 1;
  for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
          if (arr[j] < arr[i] && dp[j] + 1 > dp[i])
              dp[i] = dp[j] + 1;
      }
  }
  int max = 0;
  for (int k = 0; k < n; k++) if (dp[k] > max) max = dp[k];
  return max;
13}

Step 1/0

Practice

LeetCode·#300 Longest Increasing SubsequenceMedium HackerRank·Longest Increasing SubsequenceHard NeetCode·Longest Increasing SubsequenceMedium

BestO(n²)

AverageO(n²)

WorstO(n²)

SpaceO(n)