c++ - 找到数组中元素总和最大的子序列

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。