查找数组中元素总和最大的子序列

Question

我最近采访了一家公司,他们让我写一个算法,找到数组中元素总和最大的子序列.数组中的元素可以是负数.是否有O(n)解决方案？非常感谢任何好的解决方案.

Answer 1

如果你想要最大的序列数,那么像这样的东西可能会起作用:

$cur = $max = 0;
foreach ($seq as $n)
{
  $cur += $n;
  if ($cur < 0) $cur = 0;
  if ($cur > $max) $max = $cur;
}

这只是我的头脑,但似乎是正确的.(忽略它假定0是空和所有负集的答案.)

编辑:

如果您还想要序列位置:

$cur = $max = 0;
$cur_i = $max_i = 0; 
$max_j = 1;

foreach ($seq as $i => $n)
{
  $cur += $n;
  if ($cur > $max)
  {
    $max = $cur;
    if ($cur_i != $max_i)
    {
      $max_i = $cur_i;
      $max_j = $max_i + 1;
    }
    else
    {
      $max_j = $i + 1;
    }
  }

  if ($cur < 0)
  {
    $cur = 0;
    $cur_i = $i + 1;
  }
}

var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max);

可能有一种更简洁的方法来做到这一点.同样,它具有相同的假设(至少一个正整数).此外,它只找到第一大序列.

编辑:将其更改为使用max_j(独占)而不是max_len.

Answer 2

如果你的意思是增加最长的子序列,请参阅codaddict的答案.

另一方面,如果你的意思是找到具有最大总和的子数组(仅对负值有意义),那么有一个优雅,动态的编程风格线性时间解决方案:

http://en.wikipedia.org/wiki/Maximum_subarray_problem