找到的元素的最大总和子数组中的 [英] Find the subsequence with largest sum of elements in an array

问题描述

我最近采访了一个公司，他们让我写一个算法，发现与数组中的元素的最大一笔的序列。数组中的元素可以是负的。有没有为它O（n）的解决方案？任何一个优秀的解决方案是非常AP preciated。

I recently interviewed with a company and they asked me to write an algorithm that finds the subsequence with largest sum of elements in an array. The elements in the array can be negative. Is there a O(n) solution for it? Any good solutions are very much appreciated.

推荐答案

如果你想连续数字的最大的一笔则是这样的可能工作：

If you want the largest sum of sequential numbers then something like this might work:

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

这只是我的头顶部，但它似乎是正确的。 （忽略因为它假定0是空的，所有的负面集的答案。）

That's just off the top of my head, but it seems right. (Ignoring that it assumes 0 is the answer for empty and all negative sets.)

编辑：

如果你也想在序列中的位置：

If you also want the sequence position:

$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);

有可能是一个更简洁的方式来做到这一点。再次，它具有相同的假设（至少一个正整数）。此外，它只是找到的第一个最大的序列。

There might be a more concise way to do it. Again, it has the same assumptions (at least one positive integer). Also, it only finds the first biggest sequence.

编辑：将其改为使用 max_j （独家）而不是 MAX_LEN

changed it to use max_j (exclusive) instead of max_len.

这篇关于找到的元素的最大总和子数组中的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！