How Many Longest Increasing — Solution & Editorial

Back to the Problem

Track, per position, both the LIS length ending there and how many achieve it. On a tie in length, add the counts; on a strict improvement, replace. Sum counts over all positions attaining the global maximum. (Fenwick trees give O(N log N).)

Complexity: O(N²) here