4 ms·
Runs can be increasing or decreasing, a reversed array is a single run. Worst case is n/2 because you can always split the array in pairs (if it alternates a hi
by pxndx 8y ago
Runs can be increasing or decreasing, a reversed array is a single run. Worst case is n/2 because you can always split the array in pairs (if it alternates a high and a low value for example).
- Fri31Aug 8y agoAh I didn't know it also exploited reversed runs. Amazing.