Найти два элемента в массиве, разница между которыми максимальна (оптимизация алгоритма)

@cybercitizen · Регистрация: 22.05.2015

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

Есть правильное решение задачи. Не проходит последние тесты по времени. Задачу я уже сдал, но вопрос остался открытым. Сигнатура функции задана условием, тело нужно реализовать.

Надо найти два элемента в массиве, разница между которыми максимальна.
Ограничения:
Числа вычитаются только "справа-налево", т.е. из числа с индексом 5 мы можем вычитать только числа с индексами 0..4
Вернуть либо -1 как фейл, либо разницу разницу между найденными числами, которая наибольшая.

решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <climits>
 
int max_diff (std::vector<int> a) {
  // Enter your code here
  
  if(a.size() < 2){
    return -1;
  }
  
  int _max_index = 0;
  int _min_index = 0;
  int _max_diff = INT_MIN;
  
  for(int i = 1; i < a.size(); ++i){
    
    for(int j = 0; j < i; ++j){
      long long n = (long long)a[i] - (long long)a[j];
      
      if(n < INT_MIN){
        continue;
      }
      
      if(n > _max_diff){
        _max_diff = (int) n;
        _max_index = i;
        _min_index = j;
      }
    }
  }
  return _max_index == 0 && _min_index == 0
    ? -1
    : a[_max_index] - a[_min_index];
}

@daslex · 28.05.2015, 14:47

а какой в этом смысл если это не дает эффекта?
и с чего это сложность линейная, когда выдает приблизительно одно и то же время (например на массиве в 1000 элементов при 10000000 итерациях что линейная сложность, что квадратичная у меня работает около 7 минут).
да и подозреваю я, что здесь не линейная сложность, ведь if (val_cur >= min_cur_) diff_max_ = std::max(...); уже делает алгоритм не линейным.

@Mr.X · 28.05.2015, 15:08

Сообщение от daslex

и с чего это сложность линейная

Линейная, потому что время работы программы линейно зависит от размера массива, так как у меня обрабатывается за один цикл, а в ваших вариантах два вложенных. Если время так критично, то можно мой вариант на Си переписать, может быстрее заработать.

@daslex · 28.05.2015, 15:24

Ну так и должно быть быстрее, а не одинаковое время на массиве в 1000 элементов при 10000000 итерациях с генерацией разных массивов. Причем заметно быстрее.
А оно, можно сказать, одинаковое.

Добавлено через 4 минуты
иначе это такое же линейное как у нас квадратичное. Просто, что можно в один цикл никто не отрицал.

Добавлено через 4 минуты
Циклы в циклах - это уже не линейная сложность.

Добавлено через 22 секунды
foreach(std::max...

@mymedia · 28.05.2015, 15:32

Сообщение от daslex

foreach(std::max...

В std::max нету цикла. Это просто выбор наибольшего из двух аргументов

@daslex · 28.05.2015, 15:39

Почему на время это все не влияет?

@cybercitizen · 28.05.2015, 15:42 **[ТС]**

Сообщение от Mr.X

И?*

Переполнение. Результат неверный. Должен был быть результат 9.

@Avazart · 28.05.2015, 16:41

del

@Mr.X · 28.05.2015, 17:59

Сообщение от cybercitizen

Переполнение. Результат неверный. Должен был быть результат 9.

А проверку на переполнение вы сами выдумали или это в задаче было? Вообще-то типы выбираются так, чтобы результаты вычислений в них помещались.

Добавлено через 3 минуты

Сообщение от daslex

Почему на время это все не влияет?

Плюсовая программа может работать медленнее сишной. Я ж говорил уже - чтобы сравнить корректно надо мою программу на Си переписать.

Добавлено через 48 минут

Сообщение от cybercitizen

Должен был быть результат 9.

Ну, это вы точно сами выдумали, причем не очень удачно. Если уж и выдумывать проверку на переполнение, то логично в такой ситуации -1 возвращать, иначе что это за проверка на переполнение, если она о переполнении не сообщает, да еще и результат липовый выводит?

@cybercitizen · 28.05.2015, 18:07 **[ТС]**

Сообщение от Mr.X

Вообще-то типы выбираются так, чтобы результаты вычислений в них помещались.

Сообщение от cybercitizen

Сигнатура функции задана условием, тело нужно реализовать.

\n

Сообщение от Mr.X

Ну, это вы точно сами выдумали, причем не очень удачно. Если уж и выдумывать проверку на переполнение, то логично в такой ситуации -1 возвращать

если вычислить невозможно (например, если абсолютно все разницы не влезают в int) - вернуть -1.

@Mr.X · 28.05.2015, 18:44

Сообщение от cybercitizen

Сигнатура функции задана условием, тело нужно реализовать.

Ну, если задано, что функция возвращает int, то предполагается, что результаты вычислений в этот тип помещаются, к чему эти извращения?

@cybercitizen · 28.05.2015, 21:27 **[ТС]**

Сообщение от Mr.X

к чему эти извращения?

Пусть эта сторона вопроса тебя не волнует. Условие есть, решение должно быть корректным и соответствовать условиям.

@Mr.X · 28.05.2015, 21:34

Сообщение от cybercitizen

Пусть эта сторона вопроса тебя не волнует. Условие есть, решение должно быть корректным и соответствовать условиям.

Что-то я не помню когда мы с вами на брудершафт пили. Да и вообще ваше последнее сообщение крайне невежливо. Ведите себя прилично.

@cybercitizen · 28.05.2015, 21:42 **[ТС]**

Не по теме:

Что в нем невежливого? Не накручивай себя, я ничего дурного тебе не сказал. Просто констатирую факт. Твой вариант хороший, но не корректный. Я бы не постил тут задачу если бы она была настолько примитивна.

Добавлено через 3 минуты
Получается что страгегия поиска минимума или максимума и максимума и минимума относительно их соответственно неверна тем что ответ может не влезать в int. Следовательно надо искать другой алгоритм.

@Avazart · 28.05.2015, 21:57

Следовательно думать о том что твое задание нафиг кому сдалось, люди лишь пытаются тебе помочь и объяснить и если ты не понимаешь/ не хочешь понять/упираешься то ты сам себе злобный буратино.

@cybercitizen · 28.05.2015, 22:29 **[ТС]**

Не по теме:

Avazart, ну во-первых я ничего не требую, во-вторых насильно никого не заставляю, в-третьих представленные решения не решают задачу. Не понимаю причины наездов.
Я просто сказал что решение неверное. В ответ на это товарищ заявил что это условие видите ли неверное. Хотя речь о переполнении уже была

@Avazart · 28.05.2015, 22:33

Что не понятно? Тебе изначально сказали что проверка на переполнение ты сам придумал, собственно и сам себе злобный буратиН
сам придумал сам решай, а фекать не стоит.

@cybercitizen · 28.05.2015, 22:36 **[ТС]**

Сообщение от Avazart

если ты не понимаешь/ не хочешь понять/упираешься

Что я не понимаю? Покажи.

@Avazart · 28.05.2015, 22:37

Сообщение от cybercitizen

В ответ на это товарищ заявил что это условие видите ли неверное.

А что не так? Я бы сказал д*бильно сформулированное.

Добавлено через 50 секунд

Сообщение от cybercitizen

Что я не понимаю? Покажи.

Сообщение от Mr.X

Ну, если задано, что функция возвращает int, то предполагается, что результаты вычислений в этот тип помещаются, к чему эти извращения?

...

@cybercitizen · 28.05.2015, 22:38 **[ТС]**

Сообщение от Avazart

Тебе изначально сказали что проверка на переполнение ты сам придумал

То есть если на заборе х.. написано, то так оно стало быть и есть? Если мне сказали что я это сам придумал, значит это очевидный факт? Ну ок, я не настаиваю. Занимайся своими делами.

@Avazart · 28.05.2015, 22:43

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

Кстати никто не мешает делать проверку на переполнение, но вроде это тебе уже это предложили.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	28.05.2015, 14:47
	а какой в этом смысл если это не дает эффекта? и с чего это сложность линейная, когда выдает приблизительно одно и то же время (например на массиве в 1000 элементов при 10000000 итерациях что линейная сложность, что квадратичная у меня работает около 7 минут). да и подозреваю я, что здесь не линейная сложность, ведь if (val_cur >= min_cur_) diff_max_ = std::max(...); уже делает алгоритм не линейным. 0

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	28.05.2015, 15:24
	Ну так и должно быть быстрее, а не одинаковое время на массиве в 1000 элементов при 10000000 итерациях с генерацией разных массивов. Причем заметно быстрее. А оно, можно сказать, одинаковое. Добавлено через 4 минуты иначе это такое же линейное как у нас квадратичное. Просто, что можно в один цикл никто не отрицал. Добавлено через 4 минуты Циклы в циклах - это уже не линейная сложность. Добавлено через 22 секунды foreach(std::max... 0

@daslex 1373 / 596 / 199 Регистрация: 02.08.2011 Сообщений: 2,886
	28.05.2015, 15:39
	Почему на время это все не влияет? 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	28.05.2015, 16:41
	del 0

@cybercitizen 204 / 26 / 5 Регистрация: 22.05.2015 Сообщений: 357
	28.05.2015, 21:42 [ТС]
	Не по теме: Что в нем невежливого? Не накручивай себя, я ничего дурного тебе не сказал. Просто констатирую факт. Твой вариант хороший, но не корректный. Я бы не постил тут задачу если бы она была настолько примитивна. Добавлено через 3 минуты Получается что страгегия поиска минимума или максимума и максимума и минимума относительно их соответственно неверна тем что ответ может не влезать в int. Следовательно надо искать другой алгоритм. 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	28.05.2015, 21:57
	Следовательно думать о том что твое задание нафиг кому сдалось, люди лишь пытаются тебе помочь и объяснить и если ты не понимаешь/ не хочешь понять/упираешься то ты сам себе злобный буратино. 0

@cybercitizen
	28.05.2015, 22:29 [ТС]
	Не по теме: Avazart, ну во-первых я ничего не требую, во-вторых насильно никого не заставляю, в-третьих представленные решения не решают задачу. Не понимаю причины наездов. Я просто сказал что решение неверное. В ответ на это товарищ заявил что это условие видите ли неверное. Хотя речь о переполнении уже была 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	28.05.2015, 22:33
	Что не понятно? Тебе изначально сказали что проверка на переполнение ты сам придумал, собственно и сам себе злобный буратиН сам придумал сам решай, а фекать не стоит. 0

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	28.05.2015, 22:43
	Тут не гадалки, ты написал задание люди по нему и судят, а что там за шиза в твоей голове уже дело другое. Кстати никто не мешает делать проверку на переполнение, но вроде это тебе уже это предложили. 0