0

Решаю задачу по нахождению максимальной суммы подпоследовательности в массиве. Написал решение через рекурсию, но оно слишком медленное. Как можно его оптимизировать?

Условие задачи:

Даны число 1≤n≤10^2 ступенек лестницы и целые числа −10^4≤a[1],…,a[n]≤10^4, которыми помечены ступеньки. Найдите максимальную сумму, которую можно получить, идя по лестнице снизу вверх (от нулевой до n-й ступеньки), каждый раз поднимаясь на одну или две ступеньки.

Sample Input 1:
2
1 2
Sample Output 1:
3

Sample Input 2:
2
2 -1
Sample Output 2:
1

Sample Input 3:
3
-1 2 1
Sample Output 3:
3

Моё решение через рекурсию на C++:

#include <iostream>
#include <climits>
#include <algorithm>

#define SZ 100

using namespace std;

int n, a[SZ + 1];

int foo(int step, int sum) {

    int s1, s2;

    if (step == n)
        s1 = s2 = sum;
    else
        s1 = s2 = -INT_MAX;

    if (step + 1 <= n)
        s1 = foo(step + 1, sum + a[step + 1]);

    if (step + 2 <= n)
        s2 = foo(step + 2, sum + a[step + 2]);

    return max(s1, s2);
}

int main(int argc, const char * argv[]) {

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << foo(0, 0);

    return 0;
}
2
  • Что значит на "одну или две" как должна считаться сумма при этом? Уточните когда на одну, а когда на две.
    – Cerbo
    12 дек 2015 в 15:28
  • @Cerbo, условие приведено как есть - за что купил, за то и продаю. Я понимаю это так. Представьте себе лестницу, где на каждой ступеньке написано число. Вы становитесь перед первой ступенькой и дальше у вас есть выбор либо наступить на первую ступеньку (+1), либо сразу на вторую ступеньку (+2). Далее по такой же схеме, либо наступить на следующую ступеньку, либо пропустив её, наступить на следующую. И таким образом надо дойти до последней ступеньки. Вопрос в том на какие ступеньки наступать, а какие пропускать, чтобы набрать максимальную сумму.
    – abg
    12 дек 2015 в 16:44

2 ответа 2

1

По "положительным" ступенькам следует идти подряд.
Если попадается одна отрицательная ступенька - перепрыгнуть, если две - то прыгать на ту, где минус помельче.
Если группа отрицательных ступенек больше - включать рекурсию на минимизацию потерь, причём на каждую пару последовательных ходов должен приходиться хотя бы один прыжок через ступеньку.

0

Во-первых в Си принято индексировать массивы с 0, а не 1. Поэтому, по-людски вот так:

int a[SZ];
...
for(int i = 0; i < n; ++i) cin >> a[i];

Теперь по теме вопроса. Медленно работает потому что вы перебираете все возможные варианты прохода по лестнице, что делать совсем необязательно.

Правильное решение: всегда шагать на положительные ступеньки, если попадается отрицательная то перешагивать ее если после нее положительная, иначе если тоже отрицательная то выбирать наибольшую:

int foo(int step, int sum)
{
   if(step + 1 < n)  // можем шагнуть на две
   {
       if(a[step] >= 0 || a[step] > a[step + 1])
       {
           return foo(step + 1, sum + a[step]);
       }
       return foo(step + 2, sum + a[step + 1]);
   }
   else if(step < n) // можем на одну, то есть мы на последней ступеньке
   {
       return sum + a[step]; // мы обязаны добавить последнюю
   }

   return sum; // ступеньки кончились
}
1
  • В варианте от Cerbo считает неправильно последовательности отрицательных чисел. Например, -100 -200 -300 должно быть -400, а получится -600
    – user197012
    12 дек 2015 в 17:08

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.