以int数组的最大总和的子序列

Question

给定一个整数数组,你怎么能找到两个索引i和j,这样在索引开始和结束时子元素的总和最大化,在线性时间？

Answer 1

简单.假设你有阵列a.首先,计算数组s,在哪里s[i] = a[0]+a[1]+...+a[i].你可以在线性时间内完成:

s[0]=a[0];
for (i=1;i<N;i++) s[i]=s[i-1]+a[i];

现在,总和a[i]+a[i+1]+..+a[j]等于s[j]-s[i-1].对于固定的j,要最大化此差异的值,您应该找到最小s[i-1]范围0..(j-1).

想象一下通常的算法来找到数组中的最小值.

min = x[0];
for (j=1; j<N; j++)
  if (x[j] < min)
    min = x[j];

您迭代并比较每个数组元素min...但在每次迭代时,这min是数组中的最低值,其中索引范围是0..j!这就是我们正在寻找的东西!

global_max = a[0];
max_i = max_j = 0;
local_min_index = 0;
for (j=1; j<N; j++){
  // here local_min is the lowest value of s[i], where 0<=i<j
  if (s[j] - s[local_min_index] > global_max) {
     global_max = s[j] - s[local_min_index]
     //update indices
     max_i = local_min_index + 1;
     max_j = j;
  }
  //update local_min_index for next iteration
  if (s[j]<local_min){
    local_min = s[j];
    // update indices
    local_min_index = j;
  }
}

Answer 2

从我的编程珍珠副本:

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)