algorithm - 最大和递增子序列，改变算法以使用内存

Question

我有以下代码实现了这个问题的递归解决方案，而不是使用引用变量“x”来存储整体最大值，我怎样才能或者我可以从递归中返回结果，这样我就不必使用有助于内存的“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，假设你必须选择大于 last_taken_number 的元素来保持它的递增子序列 ，其中您想要的答案是 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)//忽略，
seq[current_index] + sum(current_index + 1, seq[current_index])//取
)。

第二个决定并不总是有效的，所以你必须确保当前元素 > 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
}