隣接するサブアレイの時間の複雑さを減らす

Question

私はこのアルゴリズムの時間の複雑さをどのように減らすことができるのだろうと思っていました。 k個の整数に合計する要素を持つmaxサブアレイの長さを計算します。

=整数のアレイ

K = maxの整数

例：A = [1,2,3]、K = 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 algorithを使用することができますこれはmです。

index 0から開始し、前方に進むにつれてサブアレイの合計を計算します。 sumがkを超えると、最初の要素を減算して合計が再びkより小さくなり、再び合計を開始します。

Pythonコードの下に検索：

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) 

OUTPUT：

2