Найдите максимальную сумму интервалов в списке действительных чисел

Вот вопросы на собеседовании, которые коллега задал на должность программиста. Я подумал, что это было здорово, чтобы посмотреть, как интервьюируемый обдумывает это. Я хотел бы получить ответы о том, как сообщество SO думает об этом.

Учитывая список реальных чисел длины N, скажем [a_1, a_2, ..., a_N] , что такое сложность нахождения максимального значения M, для которого существуют такие индексы 1 <= i <= j <= N, что

a_i + a_ {i + 1} + ... + a_j = M ?

Приношу свои извинения, если это классическая проблема CS.