在C中递归地解决问题

Question

我们的教授给了我们以下任务:

"正确"系列是其成员总和等于其第一个成员的索引的系列.

该程序应该在一系列n个数字中找到最长"正确"系列的长度.

例如:如果输入系列将是arr[4]={1, 1, 0, 0} 输出(最长的"正确"系列)将是3.
arr[0]=1. 0!=1因此这里最长的系列是0.
arr[1]=1,and 1=1.但是下面的成员也总结为1,如下所示:
1=arr[1]+arr[2]+arr[3] = 1+ 0 + 0因此这里最长的系列是3.

此示例中的输出是3.

这是我到目前为止:

int solve(int arr[], int index, int length,int sum_so_far)
{
     int maxwith,maxwithout;

     if(index==length)
         return 0;

     maxwith = 1+ solve(arr,index+1,length,sum_so_far+arr[index]);
     maxwithout = solve(arr,index+1,length,arr[index+1]);

     if(sum_so_far+arr[index]==index)
         if(maxwith>maxwithout) 
            return maxwith;

     return maxwithout;

     return 0;
}



int longestIndex(int arr[], int index,int length)
{
     return solve(arr,0,length,0);
}

我在这做错了什么？

我们不应该在这个任务中使用循环.

Answer 1

在我看来，问题就出在这里：

if(sum_so_far+arr[index]==index)

您正在将到目前为止的总和与当前索引进行比较，但您应该将其与该系列中的第一个索引进行比较。在我看来，如果从 arr 的最后一个元素开始到第一个元素，而不是按照自然顺序，会更好。这样，您就开始对元素求和，直到总和等于当前索引。