Reducing time complexity of contiguous subarray
<p>I was wondering how I could reduce the time complexity of this algorithm.
It calculates the length of the max subarray having elements that sum to the k integer.</p>

<p>a = an array of integers</p>

<p>k = max integer</p>

<p>ex: a = [1,2,3], k= 3</p>

<p>possible subarrays = [1],[1,2]</p>

<p>length of the max subarray = 2</p>

<pre><code>    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 &lt;= k and ((i+sub_total)&lt;=no_bigger) and (k&gt;=(current_sum + a[i+sub_total])):
                    current_sum += a[i+sub_total]
                    sub_total += 1
                else:
                     break
            if sub_total &gt; current_highest:
                current_highest = sub_total

        return current_highest
</code></pre>

<p>You can use <code>sliding window</code> algorithm for this.</p>

<p>Start at <code>index 0</code>, and calculate sum of subarray as you move forward. When sum exceeds <code>k</code>, start decrementing the initial elements till sum is again less than <code>k</code> and start summing up again.</p>

<p>Find below the python code:</p>

<pre><code>def max_length(a,k):
    s = 0
    m_len = 0
    i,j=0,0
    l = len(a)
    while i&lt;l:
        if s&lt;=k and m_len&lt;(j-i):
            m_len = j-i
        print i,j,s
        if s&lt;=k and j&lt;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)
</code></pre>

<p>OUTPUT:</p>

<pre><code>2
</code></pre>

python algorithm optimization