最大和递增子序列，改变算法以使用记忆

Question

我有以下代码实现了这个问题的递归解决方案，而不是使用参考变量 'x' 来存储整体最大值，我怎样才能 return 递归的结果所以我不必使用有助于记忆的 'x'?

// Test Cases: 
// Input: {1, 101, 2, 3, 100, 4, 5} Output: 106
// Input:  {3, 4, 5, 10} Output: 22

int sum(vector<int> seq)
{
    int x = INT32_MIN;
    helper(seq, seq.size(), x);
    return x;
}

int helper(vector<int>& seq, int n, int& x)
{
    if (n == 1) return seq[0];

    int maxTillNow = seq[0];
    int res = INT32_MIN;

    for (int i = 1; i < n; ++i)
    {
        res = helper(seq, i, x);
        if (seq[i - 1] < seq[n - 1] &&  res + seq[n - 1] > maxTillNow) maxTillNow = res + seq[n - 1];
    }

    x = max(x, maxTillNow);
    return maxTillNow;
}

Answer 1

首先，我不认为这个实现是正确的。对于这个输入 {5, 1, 2, 3, 4} 它给出 14 而正确的结果是 10.

为了编写此问题的递归解决方案，您不需要将 x 作为参数传递，因为 x 是您希望从函数本身获得的结果。相反，您可以构造如下状态：

当前索引：这是您在当前步骤处理的索引。
最后取的数字：这是到目前为止您在结果子序列中包含的最后一个数字的值。这是为了确保您在以下步骤中选择更大的数字以保持结果子序列增加。

所以您的函数定义类似于 sum(current_index, last_taken_number) = the maximum increasing sum from current_index until the end, given that you have to pick elements greater than last_taken_number to keep it an increasing subsequence，其中您想要的答案是 sum(0, a small value)，因为它计算整个序列的结果。 a small value 我的意思是小于整个序列中的任何其他值。

sum(current_index, last_taken_number) 可以使用较小的子状态递归计算。先假设简单情况：

N = 0，结果为 0，因为您根本没有序列。
N = 1，序列只包含一个数字，结果要么是那个数字，要么是 0，如果数字是负数（我正在考虑一个空的子序列作为一个有效的子序列，所以不取任何数字是一个有效答案）。

现在到了棘手的部分，当 N >= 2 时。

假设 N = 2。在这种情况下，您有两个选择：

要么忽略第一个数字，然后问题可以减少到 N=1 版本，其中该数字是序列中的最后一个。在这种情况下结果与sum(1,MIN_VAL)相同，其中current_index=1因为我们已经处理了index=0并决定忽略它，而MIN_VAL是我们上面提到的小值
取第一个数。假设其值为X，则结果为X + sum(1, X)。这意味着解决方案包括 X，因为您决定将其包含在序列中，加上来自 sum(1,X) 的任何结果。请注意，由于我们决定采用 X，因此我们使用 MIN_VAL=X 调用 sum，因此我们选择的以下值必须大于 X。

两项决定均有效。结果是这两者中的最大值。所以我们可以推导出一般递归如下：

sum(current_index, MIN_VAL) = max( sum(current_index + 1, MIN_VAL) // ignore, seq[current_index] + sum(current_index + 1, seq[current_index]) // take ).

第二个决定并不总是有效的，所以你必须确保当前元素> MIN_VAL才能有效。

这是该想法的伪代码：

sum(current_index, MIN_VAL){
   if(current_index == END_OF_SEQUENCE) return 0
   if( state[current_index,MIN_VAL] was calculated before ) return the perviously calculated result

   decision_1 = sum(current_index + 1, MIN_VAL) // ignore case
   if(sequence[current_index] > MIN_VAL) // decision_2 is valid
       decision_2 = sequence[current_index] + sum(current_index + 1, sequence[current_index]) // take case
   else
       decision_2 = INT_MIN

   result = max(decision_1, decision_2)
   memorize result for the state[current_index, MIN_VAL]
   return result
}

最大和递增子序列，改变算法以使用记忆

Maximum sum increasing subsequence, changing algorithm to use memoization

algorithm

recursion

memoization