lisLength<T extends Comparable<Object>> function

int lisLength<T extends Comparable<Object>>(List<T> list)

Returns length of LIS of list using comparable order, and optionally the indices of one such subsequence (reconstruction).

Implementation

int lisLength<T extends Comparable<Object>>(List<T> list) {
  if (list.isEmpty) return 0;
  final List<int> dp = List.filled(list.length, 1);
  for (int i = 1; i < list.length; i++) {
    for (int j = 0; j < i; j++) {
      if (list[j].compareTo(list[i]) < 0 && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
      }
    }
  }
  return dp.fold<int>(0, (int a, int b) => a > b ? a : b);
}