0

Дан целочисленный массив из 30 элементов. Опишите алгоритм, который находит и выводит сумму наибольшей по длине возрастающей последовательности подряд идущих элементов. Если таких последовательностей несколько, можно вывести любую из них.

Вот мой код:

#include <stdio.h>

main(){
int dig[10];
int i,sum,dlina,dlinamax,maxsum;

for (i = 0 ; i <= 4 ;i++){
   scanf("%d",&dig[i]);
}

for ( i = 0 ; i <= 9 ; i++){
   dlina = 1;
   sum = dig[i];
   if (dig[i] < dig[i + 1]){
      sum += dig[i + 1];
      dlina++;
   }
   if (dlina > dlinamax){
      dlinamax = dlina;
      maxsum = sum;
   }
}
printf("Сумма самой длинной возрастающей последовательности: %d\n",maxsum);
}

Исправил:

#include <stdio.h>

main(){
int dig[10];
int i,sum,dlina,dlinamax,maxsum;

for (i = 0 ; i <= 9 ;i++){
   scanf("%d",&dig[i]);
}
maxsum = 0;
dlinamax = 0;
for ( i = 0 ; i <= 9 ; i++){
   dlina = 1;
   sum = dig[i];
   if (dig[i] > dig[i - 1]){
      sum += dig[i];
      dlina++;
   }
   if (dlina > dlinamax){
      dlinamax = dlina;
      maxsum = sum;
   }
}
printf("Сумма самой длинной возрастающей последовательности: %d\n",maxsum);
}

теперь постоянно пишет 4

10
  • 1
    У вас выход за границы массива в цикле, да и читаете 5 элементов, а пробегаете 10. Остальные 5 - это то, что лежало в памяти до этого (мусор) 13 мая 2013 в 10:39
  • Не могу понять,как исправить.
    – rolton
    13 мая 2013 в 10:47
  • Очень просто: не выходите за границу массива в цикле, и читайте не 5, а 10 элементов. Какой из пунктов вызывает вопросы?
    – VladD
    13 мая 2013 в 10:48
  • А где я вышел за границы массива?
    – rolton
    13 мая 2013 в 10:50
  • 2
    Во-первых, вы читаете всего 5 цифр, а не 10. Во-вторых, у вас совершенно неправильный алгоритм. Эта задача решается средствами динамического программирования. Почитайте [статью][1], в которой это расписано. [1]: e-maxx.ru/algo/longest_increasing_subseq_log
    – fori1ton
    13 мая 2013 в 11:10

2 ответа 2

3

Вот как-то так:

#include <stdio.h>

void main(){
  int dig[10];
  int i,sum,dlina,dlinamax,maxsum;

  for (i = 0 ; i <= 9 ;i++){
    scanf("%d",&dig[i]);
  }
  maxsum = dig[0];
  dlinamax = 0;
  dlina = 1;
  for ( i = 1 ; i <= 9 ; i++){
    if (dig[i] <= dig[i-1]){
      if (dlina > dlinamax) {
        dlinamax = dlina;
        maxsum = sum;
      }
      sum = dig[i];
      dlina = 1;
    } else {
      sum += dig[i];
      dlina++;
    }
  }
  printf("Сумма самой длинной возрастающей последовательности: %d\n",maxsum);
}
0

Первое что ты делаешь только для первых 5ти элементов т.е. вводишь только первые 5 чисел

 for (i = 0 ; i <= 4 ;i++){
       scanf("%d",&dig[i]);
    }

Но далее

for ( i = 0 ; i <= 9 ; i++){

ты бежишь до 10го элемента, а 6-7-8-9-10 нет, ты же их не вводил ни где.

Если я правильно понимаю синтаксис С, то ошибка во втором цикле!

Ну и хорошо бы прилагать ошибки, которые возникают при работе программы!

//upd

первый же

if (dig[i] > dig[i - 1]){

не удостаивается чести на выполнение, т.к. у тебя массив от 0-9, а ты просишь его узнать про -1 элемент массива - что неправильно!

и во вторых толстых.

for ( i = 0 ; i <= 9 ; i++){
   dlina = 1;
   sum = dig[i];
   if (dig[i] > dig[i - 1]){
      sum += dig[i];
      dlina++;
   }
   if (dlina > dlinamax){
      dlinamax = dlina;
      maxsum = sum;
   }
}

Что вообще за логика работы сего кода? Он делает чушь, возьми листок бумаги и рукой все действия напиши. Вчитался в код и понял, что не хочу дальше думать. Тут нужно менять логику работы программы, криво написана. А то что выводит 4ку вполне закономерно. (возьми ручку и посчитай)

Ваш ответ

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

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