Дана последовательность (массив) целых чисел. Числа могут быть как отрицательные так и положительные. Предложите самый быстрый алгоритм поиска наибольшей суммы непрерывной последовательности.
-
Круто, хорошая задачка :) – Barmaley supports Monica 20 июл '12 в 12:11
-
Я тоже нагуглил, даже отвечать не стал =) – dzhioev 20 июл '12 в 12:21
-
Знаю только самый простой:(:(:( – sudo97 20 июл '12 в 13:31
13 ответов
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 )
Соблюдается условие, что последовательность может быть пуста. Работает за O(n).
-
Зачем делать
list()
наarray
? Лишняя память на список, вроде бы, дело вполне обошлось бы генератором. – drdaeman 20 июл '12 в 16:46 -
Может быть я ошибаюсь, но при всех отрицательных элементах массива выдаст 0, при этом должно быть максимальное из отрицательных? – anatoliy_v 6 янв '16 в 14:35
-
@anatoliy_v "Соблюдается условие, что последовательность может быть пуста." – x1Mike7x 11 май '16 в 9:17
-
Книга «Жемчужины программирования» Джона Бентли (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 <cstdint>
template<class InputIterator>
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 <iostream>
#include <iterator>
int main()
{
std::istream_iterator<int> 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;
}
Решение за 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
Вот такой алгоритм. Переменная maX
хранит максимальную последовательность, а переменная maXX
хранить непрерывную последовательность на данном шаге, и если она больше максимальной, то переменная maX
обновляется. Работает за O(n). Ниже код на C ++:
#include <iostream>
#include <algorithm>
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<<maX;
return(0);
}
Так это массив или последовательность? В последовательности есть зависимость членов. Тогда надо просто узнать, убывающая она или возрастающая. Если она убывает, идем с начала до первого нуля или отрицательного. если возрастает, то до идем с конца. Как-то так
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];
}
Пробегаемся от начала массива и на i-ом шаге храним сумму массива с 0 по i-ый элемент, а также минимальную сумму к этому шагу, которую мы когда-либо вычисляли до этого и на каждом шаге релаксируем ответ на основе этих двух чисел.
int s=0,mins=0,ans=0;
for (int i=0;i<n;i++){
s+=a[i];
mins=min(mins,s);
ans=max(ans,s-mins);
}
//ans - ответ
Сложность O(n)
Задача, на самом деле, не совсем логична. Ведь, давайте представим такой массив:
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<<sums[j]<<endl;
if(sums[j]>max) {max = sums[j]; ind=j;}
}
cout<<"The longest subarray in array begins in "<<ind+1<<" position! Sum = "<<max<<endl;
-
последовательность не обязательно должна быть возрастающая или убывающая. у нее просто должна быть сумма элементов наибольшая. например,
3, -2, 4
даст ответ5
. – Yura Ivanov 20 июл '12 в 16:32 -
Ну, так, а я про что? Я говорю, что можно тупо бить последовательность на 2-3 части и искать из кусков наиболее больший по сумме элементов. – Salivan 20 июл '12 в 16:35
-
попробуйте такой ввод: int a[16] = {-6,1,1,1,1,1,1,1,1,1,-100,1,1,1,-1,1}; – Yura Ivanov 20 июл '12 в 16:58
-
Спасибо, Юра Иванов. Я Написал новый алгоритм. Можете проверить... --- Работает =) – Salivan 20 июл '12 в 17:20
-
см. мой первый комментарий. 3, -2, 4. результат должен быть 5, у вас будет 4. – Yura Ivanov 21 июл '12 в 16:46
def hashcode(c):
if len(c) == 1: return c[0]
try:
while c[0] <= 0: # Удаляем отрицательные числа с краев
c.pop(0)
except IndexError: # Все числа в списке отрицательны или пустой список
return 0
while c[-1] <= 0:
c.pop()
summa = 0
cnew = []
for i in c:
if i * summa >= 0:
summa += i
else:
cnew.append(summa)
summa = i
cnew.append(summa) # Делаем список из сумм последовательностей чисел одного знака
num = cnew.index(max(cnew))
cnew2 = []
for i in range(0, num, 2):
cnew2.append(cnew[i] + cnew[i+1]) # Складываем соседние числа
cnew2.append(cnew[num]) # максимальный элемент оставляем без изменения
for i in range(num + 1, len(cnew), 2):
cnew2.append(cnew[i] + cnew[i+1])
return hashcode(cnew2) # Рекурсивно повторяем
import random a = [random.randint(-10, 10) for i in range(100000)] print(hashcode(a))
Вот такой алгоритм у меня придумался, конечно, я не уверен, что он самый быстрый, но, по крайней мере, немедленный. Писал на Delphi. Ещё такой вопрос: если элементы равны, то это считается последовательностью равных элементов или как? У меня так: если они изначально равны, то перехожу к следующему элементу, а если равные элементы попадутся в самой последовательности (неважно какой возрастающей или убывающей), то к такому типу последовательности они и относятся. Равные идущие подряд элементы, я бы всё-таки обрабатывал как последовательность равных элементов, но по аналогии это сделать несложно.
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
Const
N0 = 100;
Type
Massif=Array[0..N0-1] Of Integer;
Var
Mas: Massif;
i, j, u, v, n: Byte;
Sum, MaxSum: LongInt;
Function Rus(Str: String): String;
Var
i: Integer;
Begin
For i:=1 To Length(Str) Do
Case Str[i] Of
'А'..'п' : Str[i] := Chr(Ord(Str[i]) - 64);
'р'..'я' : Str[i] := Chr(Ord(Str[i]) - 16);
End;
Rus:=Str;
End;
begin
Repeat
Write(Rus('Введи размер (1 < N <= 100): N = '));
Readln(N);
Until ((N > 1) And (N < 101)); // проверяю пользователя
WriteLn(Rus('Вводи массив:'));
For i:=0 To N-1 Do // ввожу массив
Begin
Write('Mas[', i+1, '] = ');
ReadLn(Mas[i]);
End;
i:=0;
MaxSum:=Low(LongInt); // максимальная сумма
While (i < N) Do
Begin
j:=i;
Sum:=0;
If (Mas[j] < Mas[j+1]) Then // возрастающая последовательность
While (j < N) Do
Begin
Sum:=Sum + Mas[j];
If (Mas[j] > Mas[j+1]) Then Break; // если последовательность нарушена, выход
Inc(j);
End
Else If (Mas[j] > Mas[j+1]) Then // убывающая последовательность
While (j < N) Do
Begin
Sum:=Sum + Mas[j];
If (Mas[j] < Mas[j+1]) Then Break;
Inc(j);
End
Else // оба соседних элемента равны
// (это событие лучше обрабатывать как последовательность равных элементов)
Begin
Inc(i);
Continue;
End;
If (Sum > MaxSum) Then // сравниваю сумму с максимальной
Begin
MaxSum:=Sum;
u:=i; // начало последовательности
v:=j; // конец последовательности
End;
i:=j+1; // пересчитываю индекс, нарушившего последовательность, элемента
End;
WriteLn;
WriteLn(Rus('Наибольшая сумма = '), MaxSum); // вывожу результат
WriteLn(Rus('Начало = '), u+1);
WriteLn(Rus('Конец = '), v+1);
WriteLn;
WriteLn(Rus('Дави на ЭНТЕР!'));
Readln;
end.
-
2
-
@Asen2, я не понимаю в чём смысл этого комментария, но удалять его не стал. – DelphiM0ZG 20 июл '12 в 16:10
-
1
-
1Для слишком уж принципиальных пользователей, код переписал для вывода кириллицы. Когда писал, то эту неприоритетную задачу перед собой не ставил: нужен алгоритм, а не способ вывода кириллицы на консоль! – DelphiM0ZG 20 июл '12 в 17:15
Не помню я уже, как точно надо ее решать, но задача из области динамического программирования. По идее, должен быть построен массив с суммами для каждой возможной последовательности, из него выбрана максимальная сумма, а потом обратно развертывается последовательность этой суммы. У Кормена есть глава по ДП.
максимальная сумма последовательности будет тогда и только тогда, когда сложены только положительные числа. Исходя из этого пишем программу. мне лень очень писать эту программу потому что она лёгкая. объсню вкратце. сначало заполняем массив числами через цикл for. потом опять с помощью цикла for складываем только положительные числа. что то типо эого.
int n; // n это количество чисел в массиве.
int max_sum = 0; // это максимальная сумма
for (i = 0 ; i < n ; i++)
{
if (chisla[i] > 0)
{max_sum +=chisla[i];
}
}
далее просто выводим
нужную нам переменную через cout
Допустим у нас массив а[n];
Тогда вводим номер элемента с которого начнем считать суму и которым закончим.
int first, final, sumResult;
first = Console.ReadLine();
final = Console.ReadLine();
try
{
for (int i=first, i<=final; i++)
{
sumResult+=a[i];
}
}
catch(Exeption e)
{
Console.ReadLine("Введен несуществующий элемент массива");
}