找到2个相等的总和子序列，且总和最大？

第二种方法的想法是正确的，基本上可以简化背包问题。但是，您的代码似乎缺乏
明确的约定 ：该

recurse

这里是我的建议：

int recurse(int idx, intsum)

idx..n-1

A

B

C

sum+sum(A)-sum(B)=0

sum(A)

-inf

-inf

-inf== -1000

现在，您将使用该合同编写一个递归回溯，然后添加备忘录。瞧-您有一个动态的编程解决方案。

在递归回溯中，我们有两种不同的情况：

1. 没有更多要分配的元素，也没有做出选择的选择

   idx == n

   。在这种情况下，我们应该检查条件是否成立（

   sum + sum(A) - sum(B) == 0

   ，即

   sum == 0

   ）并返回答案。如果为

   sum == 0

   ，则答案为0。但是，如果为

   sum != 0

   ，则没有答案，我们应该返回永远不会被选择为答案的内容，除非对整个问题没有答案。当我们修改的返回值

   recurse

   并且不希望有额外的

   if

   s时，它不能简单地为零甚至是

   -1

   ; 它应该是一个经过修改的数字，仍然是“有史以来最糟糕的答案”。我们可以做的最大修改是将所有数字加到结果值上，因此我们应该选择小于或等于负的最大数字和（即

   -1000

   ），因为现有答案始终严格地是肯定的，而虚构的答案将始终是非肯定的。
2. 有应分发到至少一个剩余元件

   A

   ，

   B

   或

   C

   。做出选择，然后从三个选项中选择最佳答案。答案是递归计算的。

这是我的实现：

const int MAXN = 50;const int MAXSUM = 1000;bool visited[MAXN + 1][2 * MAXSUM + 1]; // should be filled with falseint dp[MAXN + 1][2 * MAXSUM + 1]; // initial values do not matterint recurse(int idx, int sum){    // Memoization.    if (visited[idx][sum + MAXSUM]) {        return dp[idx][sum + MAXSUM];    }    // Mark the current state as visited in the beginning,    // it's ok to do before actually computing it as we're    // not expect to visit it while computing.    visited[idx][sum + MAXSUM] = true;    int &answer = dp[idx][sum + MAXSUM];    // Backtracking search follows.    answer = -MAXSUM;  // "Answer does not exist" marker.    if (idx == N) {        // No more choices to make.        if (sum == 0) { answer = 0;  // Answer exists.        } else { // Do nothing, there is no answer.        }    } else {        // Option 1. Current elemnt goes to A.        answer = max(answer, arr[idx] + recurse(idx + 1, sum + arr[idx]));        // Option 2. Current element goes to B.        answer = max(answer, recurse(idx + 1, sum - arr[idx]));        // Option 3. Current element goes to C.        answer = max(answer, recurse(idx + 1, sum));    }    return answer;}