Skip to main content

Number of LIS

Learn Number of LIS (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Counting HOW MANY Longest Increasing Subsequences Exist Track TWO arrays alongside each other: length[i] = LIS length ending at i (as before), and count[i] = how many distinct LIS of that length end at i. When extending from j to i, if the new length TIES the current best at i, ADD j's count; if it BEATS it, RESET to j's count.

More lessons in Dynamic Programming