Для вычисления максимальной суммы на отрезке можно за квадратичную асимптотику просто перебрать все возможные суммы в массиве. Или за линейную асимптотику использовать метод двух указателей. Для решения задачи будем идти по массиву прибавляем к сумме значение a[r] (r — правый указатель), если сумма станет больше текущего ответа, то обновляешь ответ, если сумма стала меньше нуля, то левый указатель приравниваешь к правому, а сумму приравниваешь к нулю. Подробнее об этом методе можно узнать в EDU на Codeforces.