Максимальная сумма смежных подпоследовательностей с длиной не более k - PullRequest
Новая
       28

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

2 голосов
/ 01 апреля 2019

Я пытаюсь изменить алгоритм Кадане для решения более конкретной проблемы. 

def max_Sum(arr, length, k):
if length < k:
    print('length of array should be greater than k')

res = 0
for i in range(0, k):
    res += arr[i]

current_sum = res

for i in range(k, n):
    if k == n:
        for j in range(0, k-1):
            res += arr[j]
        current_sum = res
    else:
        current_sum += arr[i] - arr[i-k]
        print(res, current_sum)
        res = max(res, current_sum)

return res

Это код для проблемы максимального подмассива. Что я хочу сделать, так это найти максимальный подмассив с длиной не более K.

Пример: у нас есть массив A = [3, -5 1 2, -1 4, -3 1, -2], и мы хотим найти максимальный подмассив длины не более K = 9. Длина подмассива должна не ограничен в K, если есть другая длина L

В этом случае алгоритм вернет 0. Он должен вернуть 6, следуя сумме A [2: 5].

1 Ответ

1 голос
/ 01 апреля 2019

Хорошо, решение, которое работает в O (n * K), состоит в том, чтобы использовать скользящие окна для любой возможной длины <= K. Я пытался найти O (n) правильное решение, модифицирующее Кадане, но я не смог.</p> 

def best_array_fixed_k( arr, length, k ):
    total_sum = 0
    best = 0
    for x in xrange( 0, length ):
        total_sum = total_sum + arr[x]
        if x >= k:
            total_sum = total_sum - arr[x - k]
        if x >= k - 1:
            best = max( best, total_sum )
            # this makes sure that we are considering a window with length = k
    return best

def max_sum( arr, length, k):
    best = 0
    for x in xrange( 1, k + 1):
        best = max( best, best_array_for_fixed_k(arr, length, x ) )
    return best
...