Length of longest subarray of sum less than or equal to k
<p>In an interview I was asked this question: given some array of positive integers s, find the length of the longest subarray such that the sum of all its values is less than or equal to some positive integer k. Each input will always have at least one solution. The array is not circular.</p>

<p>I began writing a dynamic programming solution that worked by finding the maximum length at increasingly larger values from 0 to k.</p>

<p>Here is my code in python, there is an error inside it that I couldn't seem to find, my answer is always off by a few digits:</p>

<pre><code>def maxLength(s, k):
    lengths = [0 for x in range(k)]
    for i in range(1,k+1):
        for j in range(len(s)):
            if s[j] &lt;= i and lengths[i - s[j]] + 1 &gt; lengths[i]:
                lengths[i] = lengths[i - s[j]] + 1
        if i + 1 == len(s):
            break
    return lengths[-1]
</code></pre>

<p>Input1:<code>s = [1,2,3], k = 4</code></p>

<p>Output1: <code>2</code></p>

<p>Input2: <code>s=[3,1,2,1], k = 4</code></p>

<p>Output2: <code>3</code></p>