максимальное значение в рекурсии

Question

У меня есть домашнее задание:

Пусть P _i будет элементом arr в индексе i . Мы говорим, что индекс i «хорошо расположен», если существует индекс j ( j > = i ), так что суммирование элементы в P _i P _i + 1… P _j дает индекс i . Другими словами, индекс «хорошо расположен», если последовательность элементов, начинающаяся с этого индекса, дает индекс при суммировании.

Мы определяем «правильную длину» правильно расположенного индекса как j - i + 1 - длина последовательности, которая при суммировании показывает, что индекс хорошо размещенный. Вполне возможно, что индекс хорошо расположен с более чем одной последовательностью элементов. «Хорошо расположенная длина» в этом случае представляет собой максимальную длину различных последовательностей, определяющих индекс как «хорошо размещенные». «Максимальная длина правильного размещения» - это максимум между длиной размещения всех хорошо размещенных индексов в обр .

Если ни один индекс в массиве не является корректно размещенным, максимальная корректно расположенная длина считается равной нулю.

Это код, который я написал (он не работает):

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;
}

Answer 2

Предположим, что ваша функция longestIndex находит «максимальную правильную длину» для данного параметра length. Затем он сбрасывает его (h и l нигде не хранятся и не возвращаются, не так ли?) И вызывает себя с уменьшенным значением length. Таким образом, функция всегда будет возвращать результат либо longestIndex(arr, 0), либо longestIndex(arr, -1), который всегда будет 0.

РЕДАКТИРОВАТЬ: и функция longestIndexHelper может возвращать только 0.