Introduction

This problem is often asked with slightly inconsistent wording. If "sub-sequence" really means a contiguous slice of the array, the classic dynamic-programming answer is Kadane’s algorithm. If it means non-contiguous, the answer is different and much simpler.

Clarify the Problem First

For an array such as [4, -1, 2, 1, -5], there are two common interpretations:

• Contiguous subsequence, more commonly called a subarray.
• Non-contiguous subsequence, where you may skip elements but preserve order.

Most interview questions that ask for a dynamic-programming recurrence mean the contiguous version. That is the version discussed first here.

Dynamic Programming for the Contiguous Case

Let dp[i] be the maximum sum of a contiguous subsequence that ends exactly at index i. At each position, you either start fresh from the current element or extend the best subsequence ending at the previous index.

That gives the recurrence:

• 'dp[i] = max(arr[i], arr[i] + dp[i - 1])'

The global answer is the maximum value among all dp[i] values.

1def max_subarray_sum(arr):
2    if not arr:
3        raise ValueError("array must not be empty")
4
5    best_ending_here = arr[0]
6    best_overall = arr[0]
7
8    for value in arr[1:]:
9        best_ending_here = max(value, best_ending_here + value)
10        best_overall = max(best_overall, best_ending_here)
11
12    return best_overall
13
14
15print(max_subarray_sum([4, -1, 2, 1, -5, 4]))  # 6

This is Kadane’s algorithm. It is dynamic programming because each step reuses the solution to the previous subproblem.

Recovering the Actual Subsequence

If you also need the indices, track where the current run started and when a new best range appears.

1def max_subarray_with_indices(arr):
2    if not arr:
3        raise ValueError("array must not be empty")
4
5    best_ending_here = arr[0]
6    best_overall = arr[0]
7    start = 0
8    best_start = 0
9    best_end = 0
10
11    for i in range(1, len(arr)):
12        if arr[i] > best_ending_here + arr[i]:
13            best_ending_here = arr[i]
14            start = i
15        else:
16            best_ending_here += arr[i]
17
18        if best_ending_here > best_overall:
19            best_overall = best_ending_here
20            best_start = start
21            best_end = i
22
23    return best_overall, arr[best_start:best_end + 1]
24
25
26print(max_subarray_with_indices([4, -1, 2, 1, -5, 4]))

That is useful when the task is not only to compute the score but also to show which elements produced it.

If the Problem Is Truly Non-Contiguous

For a non-contiguous maximum-sum subsequence, the rule changes. You take every positive value, because skipping a positive number would only make the sum smaller. If all numbers are negative, the best answer is the largest single element.

1def max_non_contiguous_sum(arr):
2    positives = [value for value in arr if value > 0]
3    return sum(positives) if positives else max(arr)
4
5
6print(max_non_contiguous_sum([4, -1, 2, 1, -5, 4]))  # 11

This difference is why the problem statement matters so much. The contiguous answer is 6, while the non-contiguous answer is 11 for the same input.

Complexity

The contiguous dynamic-programming solution runs in linear time and constant extra space when you keep only the previous state. That is one reason it appears so often in interviews and competitive programming.

Common Pitfalls

• Solving the contiguous problem when the question really allows non-contiguous choices gives the wrong answer.
• Initializing the running sum to zero breaks the all-negative case.
• Building an entire dp array is unnecessary unless you need to inspect intermediate states.
• Forgetting to track indices makes it impossible to reconstruct the winning subsequence later.
• Using the word subsequence without clarifying the definition causes avoidable confusion.

Summary

• Most dynamic-programming versions of this problem mean the maximum-sum contiguous subsequence.
• Kadane’s algorithm keeps the best sum ending at the current index and updates a global best.
• The contiguous solution runs in linear time with constant extra space.
• If the problem is truly non-contiguous, sum the positive values or take the maximum element when all are negative.
• Always confirm which definition of subsequence the question intends.