Наименьшая непрерывная сумма массива с заданным диапазоном - PullRequest
Новая
       14

Наименьшая непрерывная сумма массива с заданным диапазоном

0 голосов
/ 31 марта 2020

У меня проблемы с написанием этого алгоритма, но я думаю, что у меня есть хороший gr asp, но продолжаю терпеть неудачу. Предполагается, что алгоритм возвращает наименее непрерывную сумму массива с заданным диапазоном. Например, предположим, что массив таков: [1, 3, 4, 2, -1, 5, -1, 1]. Функция получает диапазон. Для этого примера допустим, что диапазон равен 3. Цель состоит в том, чтобы найти 3 последовательных элемента с наименьшей суммой. В приведенном выше примере это будет 3. Поскольку -1 + 5 + -1 - это 3 последовательных элемента, которые дают наименьшую сумму.

Псевдокод алгоритма: 

def least_sum_search(length,dictionary):
least_sum = 0
max_range = 283
for i in dictionary:
    sum = 0
    look_ahead = length
    index = i
    if i + length > max_range:
        break
    while(look_ahead > 0):
        sum += dictionary[index]['price']
        index += 1
        look_ahead -= 1
    if(least_sum > sum):
        least_sum = sum
return least_sum

Как бы вы написали этот алгоритм? Я лично думаю, что я переосмысливаю это. Спасибо за чтение!

1 Ответ

2 голосов
/ 31 марта 2020

Допустим, у вас есть диапазон K. Вы можете держать скользящее окно из K элементов и выполнять итерацию по массиву, добавляя i-й и удаляя i-K-й элемент на каждой итерации, и сохраняя текущий минимум. Как показано ниже: 

def get_min_range(N,K,arr):
    running_sum = sum(arr[:K])
    ans = running_sum
    for i in range(K,N):
        running_sum += arr[i]
        running_sum -= arr[i-K]
        ans = min(running_sum, ans)
    return ans

print get_min_range(5,3,[1,2,3,4,5])

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

...