Very smart solution! Just some additional thought, I think the process may be tighter if we set the w = k - 1 instead of k.

When you calculate the first number in your example 2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|, you actually calculate max(max(2), max(2, 1, 3, 4)).

If you use 2, 1, 3 | 4, 6, 3 | 8, 9, 10 | 12, 56, you can use 2 only once by calculate max(max(4), max(2,1,3)). And the next one will be (4, 6), (1, 3).

It’s really smart to partition the array into two parts. In other words, we need to ensure every slice with length k will be cut into exactly two parts by partition. If we set w < k – 1, array will be like 2, 1 | 3, 4 | 6, 3 | 8, 9 | 10, 12 | 56 |, then some case like max(max(1), max(3, 4), max(6)) will have 3 parts (similar to BST when w = 2).