c - 递归中的最大值

Question

我有这个家庭作业:

Let P_i be the element of arr in index i. We say an index i is ‘well-placed’ if there exists an index j (j >= i) so that summing the elements in P_i P_i+1 … P_j yields the index i. In other words, an index is ‘well-placed’ if a sequence of elements beginning at that index yields the index when summed.

We define ‘well-placed length’ of a well-placed index to be j-i+1 – The length of the sequence that when summed shows that the index is well placed. It is possible an index is well-placed with more than a single sequence of elements. The ‘well-placed length’ in that case is the maximal length of the various sequences defining the index as ‘well-placed’. The ‘maximal well-placed length’ is the maximum between the well-placement length of all well-placed indices in arr.

If no index in the array is well-placed, the maximal well-placed length is considered to be zero.

这是我写的代码(不起作用):

int longestIndexHelper(int arr[], int i, int cur, int sum, int flag)
{
    if((arr[i]==115)||(i<0))
        return 0;
    if((sum==0)&&(flag==0))
        cur= i;
    if((sum+arr[i]==cur)&&(arr[i]<=cur))
        return longestIndexHelper(arr, i+1, i, sum+arr[i], 1)+1;
    else return 0;
}

int longestIndex(int arr[], int length)
{
    int l, h;
    if(length<=0)
        return 0;
    l= longestIndexHelper(arr, length-1, 0, 0, 0);
    h= longestIndexHelper(arr, length, 0, 0, 0);
    if(h>=l)
        return longestIndex(arr, length-1);
    else
        return longestIndex(arr, length-2);
}

我试图理解为什么它不返回最大值，我假设 IF 和 ELSE 需要定义其他事情来做...我只被允许使用这两个函数。谢谢!

Answer 1

问题似乎是你需要通过递归实现两个“循环”；一个是从给定索引开始的循环，并在运行过程中对值求和，跟踪该起始索引的最大适当长度。另一个是尝试每个可能的起始索引的循环。我看到您的辅助函数执行前者。似乎您打算调用的函数执行后者，但它没有机制来跟踪到目前为止找到的最大值或要检查的索引，与输入数组的长度分开。为此，您可能需要创建另一个辅助函数来递归遍历所有可能的起始索引。虽然我会通过扩展现有的辅助函数来实现这一点，但类似的是:

int _helper( int arr[], int len, int start, int cur, int sum, int max )
{
    if (start >= len) {
        /* game over, thanks for playing */
        return max;
    } else if (cur >= len) {
        /* try another starting index */
        return _helper( arr, len, start + 1, start + 1, 0, max );
    } else if ( sum + arr[cur] == start && max < cur - start + 1 ) {
        /* found a longer well placed length */
        return _helper( arr, len, start, cur + 1, sum + arr[cur], cur - start + 1 );
    } else {
        /* bzzzt.  try a longer length at this starting index */
        return _helper( arr, len, start, cur + 1, sum + arr[cur], max );
    }
}

int max_well_placed_length( int arr[], int len )
{
    return _helper( arr, len, 0, 0, 0, 0 );
}

#include <stdio.h>

int main(int argc, char **argv) {
    int arr[100];
    int len = 0;
    if (argc > 100) return 1;

    while (--argc) sscanf(*++argv, "%d", &arr[len++]); 

    printf("max well placed length: %d\n", max_well_placed_length(arr, len));
    return 0;
}