Найти подпоследовательность с наибольшей суммой элементов в массиве

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

Answer 3

Попробуйте следующий код:

#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 4

Полагаю, вы имеете в виду самая длинная возрастающая подпоследовательность .

Для этого не существует решения O(n).

Очень наивным решением было бы создать дублированный массив, отсортировать его в O(NlogN) и затем найти LCS отсортированногомассив и оригинальный массив, который занимает O(N^2).

Существует также решение на основе прямого DP, похожее на LCS, которое также принимает O(N^2), которое вы можете увидеть здесь .

Но если вы имели в виду увеличениепоследовательность (последовательная).Это можно сделать в O(N).

Answer 5

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 6

Если вы спрашиваете, что такое непрерывная подпоследовательность, для которой сумма максимальна, я нашел 4 алгоритма: -

1. Грубая сила: найдите все возможные суммы, используя вложенныезацикливается и продолжает обновлять maxSum, если вы найдете сумму, превышающую предыдущее установленное значение maxSum.Сложность по времени составляет O (n ^ 2)

2. Решение для динамического программирования: это удивительно элегантное решение, которое я нашел в самом StackOverflow - https://stackoverflow.com/a/8649869/2461567v - Сложность по времени: O(n), Сложность пространства: O (n)

3. DP без памяти - Алгоритм Кадане - 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)

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

Второй подход к решению этой проблемы состоит в том, что мы пройдемся по каждому элементу в массиве.У нас будут те же 2 переменные суммы и MaxSum.

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

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