logo标签列表

在一个数组中找到元素和最大的子序列

c++calgorithm
14

最近我参加了一家公司的面试，他们要求我编写一个算法，以查找数组中元素和最大的子序列。数组中的元素可以是负数。是否有O(n)的解决方案？非常感谢任何好的解决方案。

1
你的意思是“最长”的子序列吗？此外，它是“最长上升”的子序列吗？ - codaddict
2
“最长子序列”是什么意思？——哦，好的。你可能指的是：找到元素和最大的子序列。 - sellibitze
你的意思是在一个数组中找到数字序列中和最大的最长序列吗？ - jsshah
@jsshah 是的，它是具有元素和最大的子序列。 - brett
1
重复的内容：https://dev59.com/10rSa4cB1Zd3GeqPUjpl - Ignacio Soler Garcia
9个回答
16

如果你想要最大的连续数字和，那么类似这样的代码可能有效：

$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。

2
这不是他要找的。他要求一个具有最大总和的子序列。你给了他具有最大总和的连续子序列。在子序列中，数字不一定是连续的。 - Kapil D
7
@Kapil D，我的回答非常明确地开始说明它在回答什么。这是否是他的面试官想要的答案？我们永远不会知道。显然，这就是他要的答案，因为他接受了它。 （如果他真的想要一个具有最大和的子序列，答案很简单：删除所有负数。） - Matthew
是的，我知道你是为了连续编号而写的。也许提问者表述不太清楚。我喜欢你对最大序列问题的解决方案。 - Kapil D
14
如果您是指最长递增子序列，请参阅codaddict的答案。
如果您是指查找具有最大总和的子数组（仅在存在负值时才有意义），则有一种优雅的动态规划风格的线性时间解决方案：

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

1
好的链接。看起来我的回答只是那个算法的一个实现。 - Matthew
确切地说，您还需要记录开始/结束位置以返回子数组本身。当然，加 1。 - Eyal Schneider
+1...在大多数计算机科学入门课程（CS 101或CS 102）中，找到这个算法是一项常规练习。 - Konrad Rudolph
既然只需要最大和的子序列，那么它不能像这样工作吗：
  1. 首先按递减顺序对数组进行排序。
  2. 从第一个元素开始不断添加，直到遇到负值。输出到目前为止的总和，你就完成了...
 - pranavk
4
请尝试以下代码：

#include <stdio.h>

int main(void) {
    int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3};
    int cur = arr[0] >= 0? arr[0] : 0, max = arr[0];
    int start = 0, end = 0;
    int i,j = cur == 0 ? 1 : 0;
    printf("Cur\tMax\tStart\tEnd\n");
    printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
    for (i = 1; i < 10; i++) {
        cur += arr[i];
        if (cur > max) {
            max = cur;
            end = i;
            if (j > start) start = j;
        }     
        if (cur < 0) {
            cur = 0;
            j = i+1;
        }
        printf("%d\t%d\t%d\t%d\n",cur,max,start,end);
    }
    getchar();
}
3
我假设你的意思是最长递增子序列。
这个问题没有O(n)的解决方案。
一个非常简单的解决方案是创建一个副本数组，在O(NlogN)时间内对其进行排序，然后找到已排序数组和原始数组的LCS，这需要O(N^2)时间。
也有一种基于直接DP的解决方案，类似于LCS，它也需要O(N^2)的时间，你可以在这里看到。
但如果你的意思是最长递增序列（连续的），那么可以在O(N)的时间内完成。
1
void longsub(int a[], int len)  {

        int localsum = INT_MIN;
        int globalsum = INT_MIN;
        int startindex = 0,i=0;
        int stopindex = 0;
        int localstart = 0;

        for (i=0; i < len; i++) {
                if (localsum + a[i] < a[i]) {
                        localsum = a[i];
                        localstart = i;
                }
                else {
                        localsum += a[i];
                }

                if (localsum > globalsum) {
                        startindex = localstart;
                        globalsum =  localsum;
                        stopindex = i;
                }

        }

        printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum);

}
0
这个问题可以用两种不同的方法来解决。
第一种方法是使用两个变量，分别称为sum和MaxSum。

  1. 我们将继续向总和中添加值，并将其与MaxSum进行比较，如果总和的值大于MaxSum，则将总和值分配给MaxSum

  2. 如果在过程中总和的值低于0，我们将重置总和并从下一个索引开始添加新数字。以下是上述解决方案的示例代码：

    private static void FindMaxSum(int[] array)
{
    int sum = 0;
    int MaxSum = 0;

    for (int i = 0; i < array.Length; i++)
    {
        sum += array[i];

        if (sum > MaxSum)
        {
            MaxSum = sum;
        }
        else if (sum < 0)
        {
            sum = 0;
        }
    }
    Console.WriteLine("最大总和为：" + MaxSum);
}

解决这个问题的第二种方法是我们将遍历数组中的每个元素。我们将使用相同的2个变量sum和MaxSum。

  1. 首先，我们将比较总和与下一个数组元素以及总和本身的加法。无论哪个更大 - 那个值将存储在总和变量中。

  2. 接下来，我们将比较总和和MaxSum的值，谁的值更大 - 我们将把该值保存在MaxSum变量中。 示例代码如下：

    private static void FindMaxSum(int[] array)
{
    int sum = array[0], Maxsum = array[0];

    for (int i = 1; i < array.Length; i++)
    {
        sum = Max(sum + array[i], array[i]);
        Maxsum = Max(sum, Maxsum);               
    }

    Console.WriteLine("最大总和为：" + Maxsum);
}

private static int Max(int a, int b)
{
    return a > b ? a : b;
}
0

由于我们需要找到最大子序列和，我们可以：

  1. 将数组按降序排序。
  2. 取两个变量sum和maxSum。
  3. 运行一个循环直到n的长度。
  4. 当sum > maxSum时更新maxSum。

Java代码片段如下：

Arrays.sort(a, Collections.reverseOrder());
int sum = 0;
for (int i = 0; i < a.length; i++) {
 sum = sum + a[i];
     if (sum > maxSum) 
         maxSum = sum;
}
System.out.println(maxSum);

时间复杂度：O(nlogn)

-1

C函数长这样：

int largest(int arr[], int length)
{
  int sum= arr[0];
  int tempsum=0;
  for(int i=0;i<length;i++){
     tempsum+=arr[i];
     if(tempsum>sum)
        sum=tempsum;
     if(tempsum<0)
        tempsum=0;
  }
  return sum;
}
-1
如果你想知道什么是连续子序列且其和最大，我已经找到了4种算法：

  1. 暴力破解：使用嵌套循环找到所有可能的和，并在找到比先前设置的maxSum值更大的和时更新maxSum。时间复杂度为O(n^2)。

  2. 动态规划解决方案：这是一个非常优雅的解决方案，我在StackOverflow上发现了它本身-https://dev59.com/gV7Va4cB1Zd3GeqPMK8w#8649869v- 时间复杂度：O(n), 空间复杂度：O(n)

  3. 无需记忆的DP-Kadane算法-https://en.wikipedia.org/wiki/Maximum_subarray_problem - 时间复杂度：O(n)，空间复杂度：O(1)

  4. 分治解决方案-http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf 时间复杂度：O(nlgn)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接