整数数组中具有最大总和的子序列[重复]

给定一个整数数组，如何找到两个索引 i 和 j，使得子数组中从索引开始和结束的元素之和最大化，在线性时间内?

简单的。假设你得到了数组a。首先，计算数组s, where 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;
  }
}