Алгоритм поиска максимальной суммы непрерывной подпоследовательности

Дана последовательность (массив) целых чисел. Числа могут быть как отрицательны
так и положительные. Предложите самый быстрый алгоритм поиска наибольшей суммы непрерывной последовательности.    

Ответы

Ответ 1

array = list( map( int, raw_input().split() ) )
max_sum = [ 0, ]
for x in array:
    tmp = max_sum[ -1 ] + x
    if tmp < 0:
        tmp = 0
    max_sum.append( tmp )
print max( max_sum )

http://ideone.com/y3Nwd
Соблюдается условие, что последовательность может быть пуста. Работает за O(n).


Ответ 2

Решение - Алгоритм Кадане, кому интересно посмотрите ) думаю лучше уже не придумать...


Ответ 3

Книга «Жемчужины программирования» Джона Бентли (1984) подробно разбирает эту задач
(показаны O(n**3), O(n**2), O(n * log n) и наконец O(n) алгоритм). Реализация классического алгоритма Кадане на Питоне:

def maxsum(iterable):
    maxsofar = maxendinghere = 0
    for x in iterable:
        maxendinghere = max(maxendinghere + x, 0)
        maxsofar = max(maxsofar, maxendinghere)
    return maxsofar


Это O(n) (линейный однопроходной) алгоритм с O(1) (постоянной) памятью: используются только две переменные (для текущей и наибольшей суммы). Пример:

>>> maxsum([1, 2, -5, 3, 2, -1, 5, -10, 3, 2])
9


То же самое на С++:

#include 

template
intmax_t maxsum(InputIterator first, InputIterator last)
{
  intmax_t maxsofar = 0, maxendinghere = 0;
  for ( ; first != last; ++first) {
    maxendinghere = std::max(maxendinghere + *first, (intmax_t)0);
    maxsofar = std::max(maxsofar, maxendinghere);
  }
  return maxsofar;
}


Пример:

$ g++ -std=c++11     maxsum.cc   -o maxsum
$ ./maxsum <<<'1 2 -5 3 2 -1 5 -10 3 2'
9


где main():

#include 
#include 

int main()
{
  std::istream_iterator numbers(std::cin), eof;
  std::cout << maxsum(numbers, eof) << std::endl;
}


Тот же код работает и для явного массива:

int main()
{
  int a[] = {1, 2, -5, 3, 2, -1, 5, -10, 3, 2};
  std::cout << maxsum(std::begin(a), std::end(a)) << std::endl;
}


Ответ 4

Решение за O(n)
Чтобы получить максимальную сумму подпоследовательности, заканчивающейся на i-о
элементе(обозначим это значение за f(i)), нужно исключить из последовательности с 1-го по i-ый элемент префикс с минимальной суммой. Остается только найти максимум по всем f(i).
Реализация на Haskell
main = fmap (print . maxsum . map read . words) getLine

maxsum xs = let sums = scanl (+) 0 xs
                        in maximum $ zipWith (-) sums $ scanl1 min sums


Ответ 5

Вот такой алгоритм. Переменная maX хранит максимальную последовательность, а переменна
maXX хранить непрерывную последовательность на данном шаге, и если она больше максимальной, то переменная maX обновляется. Работает за O(n). Ниже код на C ++:

#include 
#include 
using namespace std;

int massiv[1000];
int maXX,maX;


int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>massiv[i];
    }

    maXX=massiv[1];
    maX=massiv[1];
    for(int i=2;i<=n;i++)
    {
        maXX=max(maXX+massiv[i],massiv[i]);
        if (maXX>maX)
            maX=maXX;

    }
    cout<
Ответ 6

Так это массив или последовательность? В последовательности есть зависимость членов
Тогда надо просто узнать, убывающая она или возрастающая. Если она убывает, идем с начала до первого нуля или отрицательного. если возрастает, то до идем с конца. Как-то так
if (mass[0] > mass[1]) {
    float sum = mass[0];
    for (int i = 1; i < count(mass); i++)
        if (mass[i] > 0)
            sum += mass[i];
} else {
    float sum = mass[count(mass) - 1];
    for (int i = count(mass) - 1; i >= 0; i--)
        if (mass[i] > 0)
            sum += mass[i];
}


Ответ 7

Пробегаемся от начала массива и на i-ом шаге храним сумму массива с 0 по i-ый элемент
а также минимальную сумму к этому шагу, которую мы когда-либо вычисляли до этого и на каждом шаге релаксируем ответ на основе этих двух чисел.
int s=0,mins=0,ans=0;
for (int i=0;i
Ответ 8

Задача, на самом деле, не совсем логична. Ведь, давайте представим такой массив:
 int a[16] = {-6,2,5,1,0,3,4,5,8,8,10,9,11,23,14,25};

Ведь его можно разделить всего на две части: первые два числа и все остальное. Пр
чем все остальное - есть непрерывная последовательность, сумма элементов которой больш
суммы первой подгруппы. Так можно делать с каждым массивом: тупо бить его на две или три части последовательно. Подумайте сами. Задача либо требует уточнений( например, максимальное количество элементов в последовательности ), либо не верна.

К примеру, я придумал такой алгоритм( Работа алгоритма производится за линейное время. Это придает алгоритму краткость и понятность. ):
(Алгоритм основан на том, что каждое отрицательное значение дает минус в сумме подгруппы )
int sums[16] = {0};
int a[16] = {-6,1,-2,0,1,1,-17,1,0,1,-100,1,1,-1,-1,1};
int n = 0;
for(int i = 0;i<16;i++)
{
    if(a[i]>=0)
    for(int j=n;j<=i;j++) sums[j]+=a[i];
    else n=i;
}
int max = 0; int ind = 0;
for(int j=0;j<16;j++)
{
    cout<max) {max = sums[j]; ind=j;} 
}

cout<<"The longest subarray in array begins in "<