max sum of list elements each separated by (at least) k elements
<p>given a list of numbers to find the maximum sum of non-adjacent elements with time complexity o(n) and space complexity of o(1), i could use this :</p>

<pre><code>sum1= 0
sum2= list[0]

for i in range(1, len(list)):
    num= sum1
    sum1= sum2+ list[i]
    sum2= max(num, sum2)

print(max(sum2, sum1))
</code></pre>

<p>this code will work only if the k = 1 [ only one element between the summing numbers] how could improve it by changing k value using dynamic programming. where k is the number of elements between the summing numbers.
for example:</p>

<p>list = [5,6,4,1,2]   k=1
answer = 11 # 5+4+2</p>

<p>list = [5,6,4,1,2] k=2
answer = 8 # 6+2 </p>

<p>list = [5,3,4,10,2]   k=1
answer = 15 # 5+10</p>

<p>Here's a quick implementation of the algorithm described by Ami Tavory (as far as I understand it). It should work for any sequence, though if your list is all negative, the maximum sum will be <code>0</code> (the sum of an empty subsequence).</p>

<pre><code>import collections

def max_sum_separated_by_k(iterable, k):
    best = collections.deque([0]*(k+1), k+1)
    for item in iterable:
        best.appendleft(max(item + best[-1], best[0]))
    return best[0]
</code></pre>

<p>This uses <code>O(k)</code> space and <code>O(N)</code> time. All of the <code>deque</code> operations, including appending a value to one end (and implicitly removing one from the other end so the length limit is maintained) and reading from the ends, are <code>O(1)</code>.</p>

<p>If you want the algorithm to return the maximum subsequence (rather than only its sum), you can change the initialization of the <code>deque</code> to start with empty lists rather than <code>0</code>, and then append <code>max([item] + best[-1], best[0], key=sum)</code> in the body of the loop. That will be quite a bit less efficient though, since it adds <code>O(N)</code> operations all over the place.</p>

python algorithm dynamic-programming