I solved this problem using a Binary indexed tree modification(read about Counter tree fenwick). It utilizes 2n memory and lets you find MAX of a subarray in logarithmic time.
My solution: 0.062s, 812 kb, yet i haven't tried to do some optimization, I used std::vector which is slower than an array. Nevertheless, I'm pretty ok with such a result