searching

LIS

Class

class LIS {
  static length(A: string): number;  static length(A: number[]): number;
  static get(A: string): string;  static get(A: number[]): number[];
}

Example

      A = carbohydrate;
Solution = abort, of length 5

Members

length

2 overloads

For simplicity will start with solely calculating the length of the Longest Increasing Subsequence(which is essentially equivalent, but simplifies the code by removing the the parent overhead code).

@complexityO(|A|^2)

@paramAstring

sequence

@returns

the length of a longest (not necessarily contiguous) subsequence of A that strictly increases

@paramAnumber[]

@returnsnumber

get

2 overloads

in the following function we store the parent pointers while calculating the length, and then reconstruct subsequence.

@paramAstring

sequence

@returns

the longest subsequence of A that strictly increases

@paramAnumber[]

@returnsnumber[]