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>It's possible to solve this with space <em>O(k)</em> and time <em>O(nk)</em>. if <em>k</em> is a constant, this fits the requirements in your question.</p>

<p>The algorithm loops from position <em>k + 1</em> to <em>n</em>. (If the array is shorter than that, it can obviously be solved in <em>O(k)</em>). At each step, it maintains an array <code>best</code> of length <em>k + 1</em>, such that the <em>j</em>th entry of <code>best</code> is the best solution found so far, such that the last element it used is at least <em>j</em> to the left of the current position.</p>

<p>Initializing <code>best</code> is done by setting, for its entry <em>j</em>, the largest non-negative entry in the array in positions <em>1, ..., k + 1 - j</em>. So, for example, <code>best[1]</code> is the largest non-negative entry in positions <em>1, ..., k</em>, and <code>best[k + 1]</code> is 0.</p>

<p>When at position <em>i</em> of the array, element <em>i</em> is used or not. If it is used, the relevant <code>best</code> until now is <code>best[1]</code>, so write <code>u = max(best[1] + a[i], best[1])</code>. If element <em>i</em> is not used, then each "at least" part shifts one, so for <em>j = 2, ..., k + 1</em>, <code>best[j] = max(best[j], best[j - 1])</code>. Finally, set <code>best[1] = u</code>.</p>

<p>At the termination of the algorithm, the solution is the largest item in <code>best</code>.</p>

python algorithm dynamic-programming