Scan From Both Ends: How One Line Took My Divide and Conquer From TLE to AC
My solution to Vlad, Misha and Two Arrays was correct and still got TLE on test 14. The fix was to check the split candidates in the order l, r, l+1, r-1, … instead of left to right. Here is why that one change turns O(n²) into O(n log n).