我已删除该问题的所有故事情节。

Q.给您N个数字。您必须找到2个相等和的子序列，且最大和。您不一定需要使用所有数字。

例如1：-

5
1 2 3 4 1

Sub-sequence 1 : 2 3 // sum = 5
Sub-sequence 2 : 4 1 // sum = 5

Possible Sub-sequences with equal sum are 
{1,2} {3}   // sum = 3
{1,3} {4}   // sum = 4
{2,3} {4,1} // sum = 5

Out of which 5 is the maximum sum.

例如2：-

6
1 2 4 5 9 1

Sub-sequence 1 : 2 4 5   // sum = 11
Sub-sequence 2 : 1 9 1   // sum = 11
The maximum sum you can get is 11

限制条件：

5 <= N <= 50

1<= number <=1000

sum of all numbers is <= 1000

Important: Only <iostream> can be used. No STLs.

N numbers are unsorted.

If array is not possible to split, print 0.

Number of function stacks is limited. ie your recursive/memoization solution won't work.

方法1：

我尝试了类似以下的递归方法：

#include <iostream>
using namespace std;

bool visited[51][1001][1001];
int arr[51];
int max_height=0;
int max_height_idx=0;
int N;

void recurse( int idx, int sum_left, int sum_right){
    if(sum_left == sum_right){
        if(sum_left > max_height){
            max_height = sum_left;
            max_height_idx = idx;
        }
    }


    if(idx>N-1)return ;

    if(visited[idx][sum_left][sum_right]) return ;

    recurse( idx+1, sum_left+arr[idx], sum_right);
    recurse( idx+1, sum_left         , sum_right+arr[idx]);
    recurse( idx+1, sum_left         , sum_right);

    visited[idx][sum_left][sum_right]=true;

    /*
       We could reduce the function calls, by check the visited condition before calling the function.
       This could reduce stack allocations for function calls. For simplicity I have not checking those conditions before function calls.
       Anyways, this recursive solution would get time out. No matter how you optimize it.
       Btw, there are T testcases. For simplicity, removed that constraint.
    */
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];

    recurse(0,0,0);

    cout<< max_height <<"\n";
}

NOTE:通过测试用例。但是超时。

方法二：

I also tried, taking advantage of constraints.

Every number has 3 possible choice:
    1. Be in sub-sequence 1
    2. Be in sub-sequence 2
    3. Be in neither of these sub-sequences

So
    1. Be in sub-sequence 1 -> sum +  1*number
    2. Be in sub-sequence 2 -> sum + -1*number
    3. None             -> sum

Maximum sum is in range -1000 to 1000. 
So dp[51][2002] could be used to save the maximum positive sum achieved so far (ie till idx).

码：

#include <iostream>
using namespace std;

int arr[51];
int N;
int dp[51][2002];

int max3(int a, int b, int c){
    return max(a,max(b,c));
}
int max4(int a, int b, int c, int d){
    return max(max(a,b),max(c,d));
}

int recurse( int idx, int sum){

    if(sum==0){
        // should i perform anything here?
    }

    if(idx>N-1){
        return 0;
    }

    if( dp[idx][sum+1000] ){
        return dp[idx][sum+1000];
    }

    return dp[idx][sum+1000] = max3 (
                                arr[idx] + recurse( idx+1, sum + arr[idx]),
                                    0    + recurse( idx+1, sum - arr[idx]),
                                    0    + recurse( idx+1, sum           )
                               )  ;

    /*
        This gives me a wrong output.

        4
        1 3 5 4
    */
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];

    cout<< recurse(0,0) <<"\n";

}

上面的代码给了我错误的答案。请帮助我解决/更正此备注。

同样也可以采用迭代方法。