сумма смежного субара изменена

Question

Для одномерного массива A размера N, который может содержать как положительные, так и отрицательные целые числа и целое число K, найти сумму смежных подмассивов чисел, которая имеет наибольшую сумму, такую, что ни один элемент в выбранном массив больше K. Это K изменяется, поскольку мы предоставляем Q запросов, каждый из которых содержит одно целое число, т.е. K.

Пример: пусть N = 5 и Q = 6, а массив - [1 2 3 4 5], а запросы:

Запрос 1: K = 5, тогда выбранный подмассив - [1,2,3,4,5]. сумма элементов = 15.

Запрос 2: K = 4, тогда выбранный подмассив - [1,2,3,4]. сумма элементов = 10.

Запрос 3: K = 3, тогда выбранный подрамник [1,2,3]. сумма элементов = 6.

Запрос 4: k = 2, тогда выбранный подмассив - [1,2]. сумма элементов = 3.

Запрос 5: k = 1, тогда выбранный подмассив является [1]. сумма элементов = 1.

Запрос 6: k = 0 as Нет элемента X в массиве A, что X < = 0. Поэтому ответ «Нет решения».

Как эффективно реагировать на эти запросы? Пожалуйста, помогите как 1 ≤ N, Q ≤ 5 * 10^5 и -10^9 ≤ Ai, K ≤ 10^9

Answer 1

Вы можете решить эту проблему линейно. Вот шаги:

1. инициализация sum=0 и maximum_sum=0
2. петли через индекс 1 до п
   - если текущее значение индекса меньше или равно K затем добавить текущее значение в sum. Если больше, то сделать sum=0
   - если текущая сумма больше maximum_sum, обновление maximum_sum
3. печати maximum_sum

Сложность: О (п)

Answer 2

Ознакомьтесь с Kadane's algorithm. При вычислении максимальной суммы субарайра необходимо не учитывать подмассивы, содержащие элементы, большие, чем K. Следовательно, при реализации алгоритма (например, возьмем код Python от Википедии) для суммы подмассива, заканчивающейся с индексом I, где array[I] > K, можно считать нулевым (. Исх доказать, что достаточно и необходимо):

def max_subarray(A): 
    max_ending_here = max_so_far = 0 
    for x in A: 
     if x > K: 
      max_ending_here = 0 
     else: 
      max_ending_here = max(0, max_ending_here + x) 
      max_so_far = max(max_so_far, max_ending_here) 
    return max_so_far