Найти максимальное произведение элементов массива, отстоящих друг от друга на расстоянии больше или равном 8

@maksvolf96 · Регистрация: 18.05.2014

Студворк — интернет-сервис помощи студентам

Задача егэ с4 ,нужно решить с минимальной сложность ,задача такова:

у нас дан массив , длинной больше 8 , нужно найти произведение максимальное произведение элементов , отстоящих друг от друга на расстоянии больше или равно 8;

вот мое решение:

C++

int max=-pow(10,9);
for(i=8;i<N;i++)
for(j=0;j<=i-8;j++)
if(a[i]*a[j]>max)
max=a[i]*a[j];

Это решение сложностью Сумма арифметической прогрессии с первым членом 8 и до N-8+1; или где то N^2...

Как я понял нужно уже на считывании обрабатывать всё, такое решение оценивается в 2 балла из 4, есть более рациональное...

Рыжий Лис · 26.02.2015, 15:58

Хм... Любопытная задачка)

C++

int max1=a[0], max2=a[8], i1=0, i2=8;
for (int i=1;i<N-8;i++){
  if (a[i]>max1){
    max1 = a[i];
    i1 = i;
  }
}
for (int i=9;i<N;i++){
  if (a[i]>max2){
    max2 = a[i];
    i2 = i;
  }
}
int max=-1;
if ((i2-i1)>=8){//повезло
  max = a[i1]*a[i2];
} else {//не повезло
  for(i=8;i<N;i++){
    for(j=0;j<=i-8;j++){
      if(a[i]*a[j]>max){
        max=a[i]*a[j];
      }
    }
  }
}

Так сходу и не придумаешь как эту задачу решить проще.
Сейчас сложность получилась примерно
* в лучшем случае: 2*N
* в худшем случае: N^2 + 2*N

Добавлено через 1 минуту
Не воспринимайте мой код всерьёз, он ужасен...

	26.02.2015, 15:58

Опции темы