Как сделать время выполнения программы равным Θ n

Question

Требование состоит в том, что ввод будет установлен в диапазоне от -5 до 5, результат должен дать самое длинное подмножество целого числа, в котором общее значение должно быть больше или равно нулю.

Я могу только придумать следующее: вход будет вход [0 до п]

let start, longestStart, end, longestEnd, sum = 0 

for i=0 to n-1 
start = i 
sum = input[i] 
    for j=1 to n 
    if sum + input[j] >= 0 then 
    end=j; 
    if end - start > longestEnd - longestStart then 
    longestStart = start; 
    longestEnd = end; 

Однако это Θ (п^2). Я хотел бы знать, каковы способы, чтобы сделать этот цикл стал Θ (п) Спасибо вам

Answer 1

С

a - b == (a + n) - (b + n) 

для любого а, б или п, мы можем применить это массив чисел , сохраняя общее количество всех элементов от 0 до текущего. Из приведенного выше уравнения сумма любого подматрицы от индекса a до b равна сумме (элементы 0-b) - sum (элементы 0-a).

Путем отслеживания локальных минимумов и максимумов и сумм к ним вы можете найти подмашину с наибольшим диапазоном за один проход, то есть O (n).