algorithm - Find the maximum interval sum in a list of real numbers

Question

Here's an interview questions that a colleague asked for a programming position. I thought this was great for watching the interviewee think it through. I'd love to get responses for how the SO community thinks of it.

Given a list of real numbers of length N, say [a_1, a_2, ..., a_N], what is the complexity of finding the maximum value M for which there exist indices 1 <= i <= j <= N such that

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

My apologies if this is a classic CS problem.

Answer 1

The complexity is just O(n) for Kadane's algorithm:

The algorithm keeps track of the tentative maximum subsequence in (maxSum, maxStartIndex, maxEndIndex). It accumulates a partial sum in currentMaxSum and updates the optimal range when this partial sum becomes larger than maxSum.