Introduction

If the goal is to find two disjoint subsequences with equal sum and make that common sum as large as possible, the problem is really a partition-style optimization problem. Order is preserved automatically by choosing indices from the original sequence, so the hard part is deciding which elements go to the first subsequence, which go to the second, and which are left unused.

Reframe the problem as balanced assignment

For each element, there are three choices:

• put it in subsequence A
• put it in subsequence B
• leave it out

The objective is:

• maximize sum(A)
• subject to sum(A) == sum(B)

That makes the problem similar to subset sum and partition, except you are allowed to discard elements. If all numbers are non-negative, the best answer is the largest equal value you can build on both sides without reusing an element.

A dynamic programming approach

One effective formulation tracks the difference between the two subsequence sums. For each processed number, keep the best achievable larger-side sum for every possible difference.

Conceptually:

• difference d = sum(A) - sum(B)
• DP state stores the maximum total on the larger side for that difference

When the difference ends at 0, both sides are equal, and that stored value is the common sum we want to maximize.

Here is a Python implementation:

1def max_equal_subsequence_sum(nums):
2    dp = {0: 0}
3
4    for x in nums:
5        current = dict(dp)
6        for diff, larger_sum in dp.items():
7            smaller_sum = larger_sum - diff
8
9            # Put x on the larger side.
10            new_diff = diff + x
11            current[new_diff] = max(current.get(new_diff, 0), larger_sum + x)
12
13            # Put x on the smaller side.
14            if x <= diff:
15                new_diff = diff - x
16                new_larger = larger_sum
17            else:
18                new_diff = x - diff
19                new_larger = smaller_sum + x
20            current[new_diff] = max(current.get(new_diff, 0), new_larger)
21
22        dp = current
23
24    return dp[0]
25
26
27print(max_equal_subsequence_sum([1, 3, 2, 4, 6]))

This returns the largest possible equal sum for two disjoint subsequences.

Why this works

At every step, the DP summarizes all useful ways to distribute processed elements without remembering the full subsequences explicitly. The difference is enough because the only thing that matters for future decisions is how far apart the two running sums are and how large the larger one already is.

This dramatically reduces the search space compared with brute force enumeration of all subsequence pairs.

If you need the actual subsequences, you can extend the DP to store parent pointers and reconstruct the choices afterward.

Example intuition

Take:

[1, 3, 2, 4, 6]

One optimal answer is:

• subsequence A = [1, 3, 2]
• subsequence B = [6]

Both sum to 6, and no larger equal sum is possible with disjoint choices in that example.

Notice that "subsequence" here does not require contiguous ranges. You only need to preserve original element order within each chosen subsequence, which is automatic when you pick indices from left to right.

Complexity and constraints

The DP complexity depends on the range of reachable sum differences. For moderate input sums, it is practical and much better than brute force.

If the numbers are very large or numerous, the state space can still grow substantially. In that case, the problem remains computationally hard in the general sense, so expectations should stay realistic.

For small input sizes, brute force or meet-in-the-middle can also be reasonable, but DP is usually the clearest exact approach.

Common Pitfalls

The biggest mistake is treating the problem as "find two subsets with the same sum" without enforcing disjointness. Each element can only be used once across the two subsequences.

Another mistake is overemphasizing contiguity. Unless the task says "subarray" or "substring," a subsequence does not need adjacent elements.

Developers also forget that maximizing the equal sum is not the same as merely finding any equal pair. A greedy choice that finds an early match can miss the optimal solution.

Finally, if negative numbers are allowed, the DP formulation and interpretation become more delicate. The straightforward positive-integer version is much easier to reason about.

Summary

• The problem is a partition-style optimization over two disjoint subsequences.
• A useful DP tracks the sum difference between the two sides.
• The best answer is the maximum common sum reachable when the final difference is zero.
• Order is not the hard part; the assignment of elements to the two sides is.
• Brute force works only for very small inputs, while DP is the standard exact approach for moderate sizes.