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

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

我假设你的意思是增长最长的子序列。

对此，没有O(n)解决方案。

很天真的解决办法是在O(NlogN)创建重复阵列，排序，然后找到排序后的数组和原始数组这需要O(N^2)的LCS。

还有一个类似于LCS的直接基于DP的解决方案，它也需要O(N^2)，你可以看到here。

但是，如果你的意思是最长的增加序列（连续）。这可以在O(N)中完成。

Answer 3

如果您的意思是最长的子序列，请参阅codaddict的答案。

如果在另一方面，你的意思是寻找具有最大总和的子阵列（才有意义负值），则是一个优雅的，动态的编程风格的线性时间的解决方案：

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

Answer 4

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; 
} 

Answer 5

试试下面的代码：

#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(); 
} 

Answer 6

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

} 

Answer 7

这个问题是可以解决两种不同的方式。

第一种方法是有两个变量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("Maximum sum is: " + MaxSum); 
   } 
   

来解决这个问题的第二种方法是，我们将通过每阵列中的每个元素。我们将有和sum和MaxSum相同的2个变量。

1. 首先，我们将和下一个数组元素和总和本身进行比较。谁更伟大 - 该值将被存储在sum变量中。

2. 接下来我们将比较sum和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("Maximum sum is: " + Maxsum); 
   } 
   
   private static int Max(int a, int b) 
   { 
       return a > b ? a : b; 
   } 
   

Answer 8

如果你问的是一个连续的子序列，其总和是最大的，我已经找到4个交易算法迄今： -

1. Brute-force：使用嵌套循环查找所有可能的总和，如果发现总和大于先前设置的maxSum设置值，则继续更新maxSum。时间复杂度为O（n^2）

2. 动态规划解决方案：这是一个非常优雅的解决方案，我在计算器上自己发现 - https://stackoverflow.com/a/8649869/2461567v - 时间复杂度：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）