Не смог решить задачку

Задача: Найти наибольшую сумму строго возрастающей подпоследовательности в исходной последовательности.

На вход дается 2 строки:

1) Количество членов последовательности

2) Сама последовательность

Пример:

6

5 2 4 3 7 7

Вывести наибольшую сумму:

Пример:

13 (2+4+7 = 13)

 

Мое решение в системе прошло несколько тестов. Еще раз прогнать через тесты возможности нет. У меня есть подозрение, что я накосячил с границами в циклах.

 

Решение:

https://pastebin.com/EYrq0sYc

Давай напишу тебе на плюсах. Вход в каком формате? Массив int?

DerRauch сказал(а):↑

Давай напишу тебе на плюсах. Вход в каком формате? Массив int?

Нажмите, чтобы раскрыть...

Мне бы лучше указать где я ошибся. Сейчас я не могу прогнать программу через тесты, так что пользы от твоего решения не будет)

Временно del

DerRauch сказал(а):↑

Временно del

Нажмите, чтобы раскрыть...

Да, вот что получается:

гарантируется ли что существует строго возрастающая последовательность из трёх членов?

VovkaKalibrovka сказал(а):↑

гарантируется ли что существует строго возрастающая последовательность из трёх членов?

Нажмите, чтобы раскрыть...

Нет, не гарантируется. Количество членов 1<бесконечность, разумеется, если это не выходит за рамки данной последовательности.

Ошибся в логике решения, т.к. сразу берёшь число в подпоследовательность, если больше текущего, а это не всегда оптимальное решение (пример: 1 3 2 2 2. 1+3 = 4, 1+2+2+2 = 7). Задача решается через динамическое программирование

numberOf = int(input())

arr = input().split()

resultedArr = []

for i in range(0, numberOf):

    counter = int(arr)

    maxi = int(arr)

    for j in range(i+1, numberOf):

        if(maxi < int(arr[j])):

             counter += int(arr[j])

             maxi = int(arr[j])

    resultedArr.append(counter)

maximum = resultedArr[0]

for i in range(1, len(resultedArr)):

    if(maximum < resultedArr):

        maximum = resultedArr

print(maximum)

Ты сравнивал очередное число последовательности с суммой. Нужно было его сравнивать с предыдущим членом новой последовательности.

lazium сказал(а):↑

Ошибся в логике решения, т.к. сразу берёшь число в подпоследовательность, если больше текущего, а это не всегда оптимальное решение (пример: 1 3 2 2 2. 1+3 = 4, 1+2+2+2 = 7). Задача решается через динамическое программирование

Нажмите, чтобы раскрыть...

подпоследовательность должна СТРОГО возрастать, то есть я не могу к 2 прибавить 2, только число больше 2.

DerRauch сказал(а):↑

numberOf = int(input())

arr = input().split()

resultedArr = []

for i in range(0, numberOf):

    counter = int(arr)

    maxi = int(arr)

    for j in range(i+1, numberOf):

        if(maxi < int(arr[j])):

             counter += int(arr[j])

             maxi = int(arr[j])

    resultedArr.append(counter)

maximum = resultedArr[0]

for i in range(1, len(resultedArr)):

    if(maximum < resultedArr):

        maximum = resultedArr

print(maximum)

 

Ты сравнивал очередное число последовательности с суммой. Нужно было его сравнивать с предыдущим членом новой последовательности.

Нажмите, чтобы раскрыть...

точно, как я до этого не додумался

спасибо за помощь.

sinkari сказал(а):↑

подпоследовательность должна СТРОГО возрастать, то есть я не могу к 2 прибавить 2, только число больше 2.

Нажмите, чтобы раскрыть...

Хорошо, не заметил условие на строгость. Тогда пример 1 5 2 3 4. 1+5 = 6 < 10 = 1+2+3+4. Не всегда нужно сразу брать член подпоследовательности, если он больше предыдущего.

lazium сказал(а):↑

Хорошо, не заметил условие на строгость. Тогда пример 1 5 2 3 4. 1+5 = 6 < 10 = 1+2+3+4. Не всегда нужно сразу брать член подпоследовательности, если он больше предыдущего.

Нажмите, чтобы раскрыть...

понял о чем ты

Задача решается через два массива, в которых на i-ой позиции ты будешь хранить максимально возможную сумму подпоследовательности для первых i членов массива и последний член подпоследовательности соответственно. Тогда для каждого i+1 члена легко определить максимальную сумму по предыдущим значениям. Последняя сумма и будет ответом

тему можно клоз

Спасибо  @lazium  @DerRauch

sinkari сказал(а):↑

тему можно клоз

Спасибо  @lazium  @DerRauch

Нажмите, чтобы раскрыть...

 

можно же отсортировать массив для начала, а потом просто идти с конца и брать элементы, не равные предыдущему?

 

Таким образом у тебя будет сложность n*logn, а не n2, и код намного проще, разве нет?

 

А не, нельзя же сортировать здесь, затупил, сорри

lazium сказал(а):↑

Задача решается через два массива, в которых на i-ой позиции ты будешь хранить максимально возможную сумму подпоследовательности для первых i членов массива и последний член подпоследовательности соответственно. Тогда для каждого i+1 члена легко определить максимальную сумму по предыдущим значениям. Последняя сумма и будет ответом

Нажмите, чтобы раскрыть...

Можешь подсказать, как это реализовать, а то я чет не вкуриваю)

DerRauch сказал(а):↑

Можешь подсказать, как это реализовать, а то я чет не вкуриваю)

Нажмите, чтобы раскрыть...

К слову, из-за условия строгой монотонности подпоследовательности можно обойтись всего одним массивом суммы.

0. Заводим массив размером с массив входных данных.

1. Заполняем нулевой индекс массива. Очевидно, что сумма для нулевого элемента равна нулевому элементу (подпоследовательность из одного элемента).

2. Дальше заполняем i+1 индекс -- идём в цикле по предыдущим значениям массива суммы (от 0 до i) и ищем максимум среди тех индексов, для которых элементы оригинального массива меньше текущего элемента. В итог записываем сумму максимального значения и текущего элемента.

3. После заполнения всего массива сумм, самая последняя сумма и будет ответом.

lazium сказал(а):↑

2. Дальше заполняем i+1 индекс -- идём в цикле по предыдущим значениям массива суммы (от 0 до i) и ищем максимум среди тех индексов, для которых элементы оригинального массива меньше текущего элемента. В итог записываем сумму максимального значения и текущего элемента.

Нажмите, чтобы раскрыть...

Сори, не понимаю этот шаг(

ищем максимум среди тех индексов, для которых элементы оригинального массива меньше текущего элемента

то есть ищем такие элементы массива сумм, чтобы сумма подпоследовательности до i элемента была меньше самого элемента? Как это возможно?

 

string str;

 cout << "Vvedite posledovatel'nost chisel cherez probel: "; 

 getline(cin, str);

 vector a;

 ToVectorInt(str, a);

 vector b;

 for (int i = 0; i < a.size(); i++)

 {

  b.push_back(0);

 }

 b[0] = a[0];

 int max = b[0];

 cout << b[0] << ' ';

 for (int i = 1; i < a.size(); i++)

 {

  if (a[i-1] < b[i-1] && max < b[i-1]) 

  {

   max = b[i-1];

  }

  b = max + a;

  cout << b << ' ';

 }

 

 

Поправь код, пожалуйста, м б так пойму.

DerRauch сказал(а):↑

 b[0] = a[0];

 cout << b[0] << ' ';

 for (int i = 1; i < a.size(); i++) {

     int max_idx = -1;

     for (int j = 1; j < i; j++) {

         if ( (a > a[j]) &&

              ((max_idx == -1) || (b[j] > b[max_idx]))

             max_idx = j;

    }

    b = (max_idx == -1) ? a : b[max_idx] + a;

    cout << b << ' ';

 }

Нажмите, чтобы раскрыть...

Как-то так, полагаю

lazium сказал(а):↑

Как-то так, полагаю

Нажмите, чтобы раскрыть...

Да, спасибо, работает. Сейчас буду разбираться)

Ток вот так

b[0] = a[0];

 int max_idx;

 cout << b[0] << ' ';

 for (int i = 1; i < a.size(); i++) {

  max_idx = -1;

  for (int j = 1; j < i; j++) {    if ((a > a[j]) &&((max_idx == -1) || (b[j] > b[max_idx])))

    max_idx = j;

  }   b = (max_idx == -1) ? a : b[max_idx] + a;

   cout << b << ' ';

 }

 

 

@lazium 

А хотя, не совсем работает

Спойлер:

язык  строго c# или с++ ?

 

DerRauch сказал(а):↑

@lazium 

А хотя, не совсем работает

Нажмите, чтобы раскрыть...

int main()

{

    int N = 0;

    scanf("%d", &N);

    int* a = new int[N];

    int* b = new int[N];

    for (int i = 0; i < N; i++) {

        scanf("%d", &(a));

        b = 0;

    }

    b[0] = a[0];

    printf("%d", b[0]);

    for (int i = 1; i < N; i++) {

        int max_idx = -1;

        for (int j = 0; j < i; j++) {

            if ( (a > a[j]) && \

                 ((max_idx == -1) || (b[j] > b[max_idx])))

                max_idx = j;

        }

        

        b = (max_idx == -1) ? a : b[max_idx] + a;

        printf(" %d", b);

    }     printf("\n%d", b[N-1]);

    delete[] a;

    delete[] b;

    return 0;

}

 

 

Под спойлером ссылка на онлайн-компилятор. Вкратце: подправил инициализацию второго индекса j с 1 на 0.

Спойлер:

http://cpp.sh/9d64f