Максимальная сумма смежных подпоследовательностей x элементов

Итак, я придумал вопрос, который я искал и искал, но не нашел ответа... Какой лучший (и говоря лучший, я имею в виду самый быстрый) способ получить максимальную непрерывную сумму подпоследовательности x элементы?

Представьте, что у меня есть: A[] = {2, 4, 1, 10, 40, 50, 22, 1, 24, 12, 40, 11, ...}. И тогда я спрашиваю:

"What is the maximum contigous subsequence on array A with 3 elements?"

Пожалуйста, представьте это в массиве с более чем 100000 элементов... Кто-нибудь может мне помочь?

Спасибо за ваше время, и вы помогаете!


sum max subsequence elements contiguous
person Fábio Colaço    schedule 08.08.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я погуглил и нашел это:

Используя подход «разделяй и властвуй», мы можем найти максимальную сумму подмассива за время O (nLogn). Ниже приведен алгоритм «разделяй и властвуй».

Алгоритм Кадане для этой задачи требует O(n) времени. Следовательно, алгоритм Кадане лучше подхода «Разделяй и властвуй».

См. код:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far
person Josh Beam    schedule 08.08.2015
comment
Это не совсем то, что я ищу, потому что мне нужна максимальная сумма, сгруппированная по X элементам... Представьте, что в моем примере выше максимальная сумма - это все элементы, поскольку все они положительные, но я хочу, чтобы максимальная сумма сгруппировалась на 3 элемента... Итак: будет 40 50 22. - person Fábio Colaço; 08.08.2015