Introduction

This problem asks you to choose array elements so the total sum is as large as possible, with one constraint: you may not select more than k consecutive elements. That makes it a dynamic-programming problem, because the best choice at position i depends on how many consecutive elements have already been selected immediately before it.

Core Sections

Define the state correctly

A one-dimensional recurrence is usually not enough for this problem because the decision at each index depends on the current run length of chosen adjacent elements. A better state is:

• 'dp[i][c] = the best sum after processing the first i elements, where c is the number of consecutive selected elements at the end'

Here:

• 'i goes from 0 to n'
• 'c goes from 0 to k'
• 'c = 0 means the ith processed position was not selected, so the run resets'

This state captures exactly the information needed for the next decision.

The recurrence

At each element arr[i], you have two choices.

1. Skip it. Then the run length resets to 0.
2. Take it. Then the previous run length must have been less than k, and the new run length becomes the previous run length plus 1.

That gives a natural transition.

1def max_sum_with_k_adjacent(arr: list[int], k: int) -> int:
2    n = len(arr)
3    neg_inf = float("-inf")
4
5    dp = [[neg_inf] * (k + 1) for _ in range(n + 1)]
6    dp[0][0] = 0
7
8    for i in range(n):
9        for run in range(k + 1):
10            if dp[i][run] == neg_inf:
11                continue
12
13            # Skip current element.
14            dp[i + 1][0] = max(dp[i + 1][0], dp[i][run])
15
16            # Take current element if run length limit allows it.
17            if run < k:
18                dp[i + 1][run + 1] = max(
19                    dp[i + 1][run + 1],
20                    dp[i][run] + arr[i]
21                )
22
23    return max(dp[n])
24
25
26print(max_sum_with_k_adjacent([3, 2, 7, 10, 12], 2))
27print(max_sum_with_k_adjacent([5, 1, 1, 5], 1))

This works for positive, mixed, and negative arrays because the skip transition is always available.

Why the state works

The reason this dynamic program is correct is that the future only needs to know one thing about the past: how many chosen elements are currently adjacent in a row. It does not need the full history.

That is the standard dynamic-programming pattern:

• keep only the information required for the next decision
• discard the rest

If you try to compress the problem into a simpler recurrence without tracking run length, you usually lose the ability to enforce the adjacency limit correctly.

Time and space complexity

The table has n * (k + 1) states, and each state performs constant work. So:

• time complexity is O(nk)
• space complexity is O(nk) for the full table

You can reduce space to O(k) by keeping only the previous row, because each row depends only on the one before it.

1def max_sum_with_k_adjacent_optimized(arr: list[int], k: int) -> int:
2    neg_inf = float("-inf")
3    prev = [neg_inf] * (k + 1)
4    prev[0] = 0
5
6    for value in arr:
7        curr = [neg_inf] * (k + 1)
8        for run in range(k + 1):
9            if prev[run] == neg_inf:
10                continue
11
12            curr[0] = max(curr[0], prev[run])
13            if run < k:
14                curr[run + 1] = max(curr[run + 1], prev[run] + value)
15        prev = curr
16
17    return max(prev)

The optimized version is usually the better production implementation.

Relationship to the classic house-robber problem

If k = 1, the problem becomes a familiar special case: you may not take two adjacent elements. That is essentially the classic house-robber constraint.

For larger k, the problem generalizes from “no two adjacent” to “no run longer than k.” Thinking of it that way helps when you sanity-check the recurrence.

Common Pitfalls

• Using a one-dimensional recurrence that ignores the current run length usually enforces the wrong constraint.
• Assuming the problem is trivial when all numbers are positive misses the fact that long runs still have to be broken once they exceed k.
• Forgetting the skip transition makes the algorithm unable to reset the consecutive count.
• Hard-coding the logic for k = 1 and then trying to generalize it without redesigning the state usually fails.
• Ignoring negative values can produce incorrect logic if the algorithm assumes taking more elements is always better.

Summary

• The right dynamic-programming state must track how many selected elements are currently adjacent in a row.
• A clean recurrence is O(nk) in time and can be reduced to O(k) space.
• The key transitions are “skip and reset the run” or “take and extend the run if allowed.”
• The classic non-adjacent maximum-sum problem is the special case k = 1.
• Once the state is defined correctly, the implementation becomes straightforward and reliable.