Учитывая интервал, нахождение наибольшей суммы чисел в массиве

Скажем, у нас есть массив с некоторыми числами в нем, и нам дано значение d (где d ›= 1), которое диктует определенный требуемый индекс. Как найти наибольшую сумму значений, ограниченных d. Вот пример:

arr = [3000, 4000, 2000, 2500, 3500, 5000]
d = 3

Вернет 4000 + 5000 = 9000 (поскольку между этими двумя числами расстояние не менее 3). Но в этом случае:

arr = [3000, 4000, 2000, 2500, 3500, 5000]
d = 2

Вернет 4000 + 2500 + 5000 = 11500.

edit: Больше объяснений. Нам нужно найти максимально возможную сумму в массиве. Единственная хитрость заключается в том, что мы не можем включать числа, меньшие индекса d. Во втором примере мы могли бы просто просуммировать все числа, чтобы получить наибольшее значение, но, поскольку мы ограничены d = 2, мы должны выбрать комбинацию, в которой числа не находятся на расстоянии ‹ 2. Другой пример может включать 3000 + 2500 + 5000 = 10500. Если вы посмотрите на мое второе решение, то 11500 > 10500, следовательно, это не оптимальный ответ.


python-3.x algorithm maximization subsequence
person Community    schedule 18.04.2021    source источник
comment
Не могли бы вы объяснить 2-й случай?   -  person Kazi Sohan    schedule 18.04.2021
comment
Я думаю, что язык должен быть подтянут. Как данность, его можно интерпретировать по-разному. Я не знаю, например, что означает «ограниченный d».   -  person Howlium    schedule 18.04.2021
comment
Я считаю, что идея состоит в том, чтобы найти подпоследовательность с максимальной суммой [A[i1], A[i2], ...], такую, что разница между каждым индексом составляет не менее d.   -  person augurar    schedule 18.04.2021
comment
ваш вопрос нуждается в дополнительных разъяснениях   -  person zazz    schedule 18.04.2021

Ответы (2)


arrow_upward
1
arrow_downward

Эта проблема может быть эффективно решена с помощью подхода динамического программирования.

Пусть A будет входным массивом, а d будет размером промежутка. Затем вы можете построить массив B таким образом, что B[i] будет максимальной суммой для первых i+1 элементов A. Вы можете вычислить элементы B простым повторением, и последний элемент содержит решение:

def solve(A, d):
    n = len(A)
    B = [0] * n
    B[0] = A[0]
    for i in range(1, d):
        B[i] = max(A[i], B[i-1])
    for i in range(d, n):
        B[i] = max(A[i] + B[i-d], B[i-1])
    return B[-1]
person augurar    schedule 18.04.2021

arrow_upward
0
arrow_downward

Вы можете сделать это за один проход, последовательно вычисляя наилучшую сумму для каждого префикса.

Как только вы получите наилучшую сумму для каждого префикса до i, но не включая его, для i наилучшая сумма либо не будет включать элемент i (и, таким образом, будет равна prefix_sums[i - 1]), либо будет включать элемент i и, таким образом, будет равна i + prefix_sums[i - d] (получить элемент i и наилучшая сумма элементов, которые находятся не менее чем в d от i-го элемента).

a = [3000, 4000, 2000, 2500, 3500, 5000]
d = 2

prefix_sums = [a[0]]
for x in a[1:]:
    cur = x if len(prefix_sums) < d else x + prefix_sums[-d]
    cur = max(cur, prefix_sums[-1])
    prefix_sums.append(cur)

print(max(prefix_sums))
person Ishamael    schedule 18.04.2021