给出了一个整数向量，我需要找到彼此相距超过 3 个位置的数字序列的最大总和。举个例子：
Input: 10, 5, 6, 7, 16, 18, 12
Output: 29
Explanation:
candidate "routes":
10-7-12 = 29
10-16 = 26
10-18 = 28
5-16 = 21
5-18 = 23
5-12 = 17
...
16
18
12
我想使用递归来解决这个问题，我已经到了程序测试所有数字超过 3 个位置的路径的地步。但是，它无法测试从同一数字开始的所有路径。 这是我的代码：
#include <iostream>
using namespace std;
const int n = 7;
int sum = 0;
int temp=0;
void rec(int (*arr), int ind){
if (ind > n-3){
if(temp > sum)
sum = temp;
temp=0;
return;
}
temp += arr[ind];
cout<<arr[ind]<<" ";
for(int i=3;i<n;i++)
rec(arr, ind+i);
cout<<endl;
}
int main(){
int arr[n] = {10, 9, 9, 9, 8, 8, 7};
for(int i=0;i<n;i++)
rec(arr, i);
cout<<endl<<endl<<"Max: "<<sum;
return 0;}
输出：
10 9 7
8
8
7
9 8
8
7
9 8
7
9 7
8
8
7
Max: 26
即使在这种情况下输出是正确的，您也可以看到它只测试 10-9-7，而不是其他 10-8、10-8 和 10-7。似乎它甚至没有进入我递归调用该函数的第一个 for 循环。
我是否理解了错误，或者我如何完成它测试所有超过 3 个位置的对？
这里有3个问题：
<小时 />根据您的输出：
10 9 7
8
8
⋮
您的代码实际上遍历所有可能的路由。而不是将你的二线8和三线8视为两条完整的路线，它们实际上是从你的第一条溃10 9 7衍生出来的。所以真的可以这样想：
10 --- 9 --- 7
`- 8
`- 8
`- 7
9 --- 8
`- 8
`- 7
⋮
这实际上不是您的输出。插入您的代码，我得到了我的输出：
10 9
8
9 8
9
9
8
Max: 19
它没有经过所有路线的原因是因为您的线路：
if (ind > n-3)
{
⋮
return;
}
您过早地终止循环。相反，您应该只在它超出索引之前结束它。所以它应该是：
if (ind > n - 1)
{
⋮
}
你的逻辑实际上有缺陷。
因为一旦达到数组中最后一个可能的数字，您总是将temp设置回 0，所以您实际上丢失了之前总和的一部分。您可以轻松创建使其失败的序列，例如：10, 9, 9, 7, 8, 20, 7。
与其将temp作为全局，不如将其设置为本地，并传递给每个递归。
为此，您需要将temp添加为rec函数的参数，并像这样调用它：
void rec(int (*arr), int ind, int temp)
{
⋮
rec(arr, i, temp);
⋮
}
int main()
{
⋮
rec(arr, i, 0);
⋮
}
或者，如果您想在main中保持签名相同，您还可以在rec中添加默认参数：
void rec(int (*arr), int ind, int temp = 0)
旁注，我会考虑使用std::array或std::vector而不是 c 样式数组，以避免全局大小n或在函数中传递int (*arr)。此外，您可以轻松地将arr制作为更长的序列。