Why does my solution TLE on the last test case?

A single pass with a running value is enough here. Keep track of the best answer so far and update it as you scan, which gives O(n) time and O(1) extra space.