Following this episode, I did find an AVX2 implementation of the maximum subarray sum that's about 25% faster than the sequential version, published here: https://gist.github.com/mlochbaum/b6e9701c6c1c617a2c2a4fb107...

Troels Henriksen (Futhark developer) pointed out to me that in expanding the state to make the scan associative I'd reinvented a fairly well-known method. The transformation from a specification as "maximum over the sums of each subarray" to the associative scan is very often used as an example of the power of the Bird-Meertens formalism or Squiggol[0], and some newer papers have demonstrated that it can be derived automatically, although not very quickly. Troels also wrote a simpler ISPC[1] implementation[2] that tested slower than C on an older CPU and faster on a newer one. Then I translated that to BQN and found it was about 4x slower than sequential C.

[0] https://en.wikipedia.org/wiki/Bird%E2%80%93Meertens_formalis...

[1] https://ispc.github.io/index.html

[2] https://gist.github.com/athas/f016084ea749602476b96c05ae415a...