algorithm - 在实数列表中找到最大区间和

Question

这是一位同事要求的编程职位的面试问题。我认为这非常适合观看受访者思考。我很想听听 SO 社区对此的看法。

给定一个长度为 N 的实数列表，比如 [a_1, a_2, ..., a_N]，找到存在索引 1 < 的最大值 M 的复杂度是多少？ = i <= j <= N 这样

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

如果这是一个经典的 CS 问题，我深表歉意。

Answer 1

复杂度是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.