This is an \$O(n \sqrt n)\$ solution to the the following problem:
Given a sequence, compute the number of non-empty increasing subsequences
The algorithm is to compute
g(i) = # of increasing subsequences that end at index i using dynamic programming, and then sum over
i. A full description of the algorithm used can be found here. However, naively using dynamic programming yields an \$O(n^2)\$ solution, which is too slow. It's possible to get \$O(n \log n)\$ using a BIT, but I opted for the \$O(n \sqrt n)\$ "hacker's" BIT, implemented below. As I am a novice (relatively), my question is: how could I have implemented it better? Specifically, I generally prefer to program in a more functional style, but this code is very imperative. How could I have made it more functional?
from math import sqrt from bisect import bisect_left def count_sequences(seq): # Normalize seq seq_sorted = sorted(seq) seq = list(map(lambda x: bisect_left(seq_sorted, x), seq)) # Initialize the memoization arrays n = len(seq); f = *n nn = int(sqrt(len(seq))); ff = *(nn+2) # Compute g(i) = f(s[i]) for s in seq: res = sum([ 1, sum(ff[: (s // nn)]), sum(f[(s // nn)*nn : s]) ]) f[s] += res ff[s // nn] += res # Sum all g(i) return sum(ff)