在实数列表中查找最大间隔总和

Question

这是一位同事要求编程职位的面试问题.我认为这对于观看受访者的思考非常有用.我很想得到SO社区如何看待它的回应.

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

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

如果这是一个典型的CS问题我很抱歉.

Answer 1

对于Kadane的算法,复杂性只是O(n):

该算法跟踪暂定的最大子序列(maxSum, maxStartIndex, maxEndIndex).currentMaxSum当该部分和大于时,它累积部分和并更新最佳范围maxSum.

Answer 2

它是O(N):

int sum = 0;
int M = 0;  // This is the output
foreach (int n in input)  {
  sum += n;
  if (sum > M)
      M = sum;

  if (sum < 0)
    sum = 0;
}

这个想法是保持自上次重置以来遇到的所有整数的总和.当总和低于零时发生复位 - 即当前间隔中有太多负数使其可能是最佳值.