Сокращение временной сложности смежного подмассива

Question

Мне было интересно, как я мог бы уменьшить временную сложность этого алгоритма. Он вычисляет длину максимального подмассива с элементами, которые суммируются с целым числом k.

а = массив целых чисел

к = макс целого

например: а = [1,2,3], к = 3

возможных подмассивы = [1], [1 , 2]

длина макс подмассива = 2

sys.setrecursionlimit(20000) 

    def maxLength(a, k): 
     #a = [1,2,3] 
     #k = 4 
     current_highest = 0 
     no_bigger = len(a)-1 
     for i in xrange(len(a)): #0 in [0,1,2] 
      current_sum = a[i] 
      sub_total = 1 
      for j in xrange(len(a)): 
       if current_sum <= k and ((i+sub_total)<=no_bigger) and (k>=(current_sum + a[i+sub_total])): 
        current_sum += a[i+sub_total] 
        sub_total += 1 
       else: 
        break 
      if sub_total > current_highest: 
       current_highest = sub_total 

     return current_highest 

Answer 1

Вы можете использовать sliding window Алгоритм Построения м для этого.

Начните с index 0 и вычислите сумму подмашины при движении вперед. Когда сумма превышает k, начните декремент исходных элементов до тех пор, пока сумма не станет меньше k и начните суммирование снова.

Поиск ниже код питона:

def max_length(a,k): 
    s = 0 
    m_len = 0 
    i,j=0,0 
    l = len(a) 
    while i<l: 
     if s<=k and m_len<(j-i): 
      m_len = j-i 
     print i,j,s 
     if s<=k and j<l: 
      s+=a[j] 
      j+=1 
     else: 
      s-=a[i] 
      i+=1 
    return m_len 

a = [1,2,3] 
k = 3 
print max_length(a,k) 

ВЫВОД:

2