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

@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];
}

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

Я прошу администрацию почистить тему от флуда. А для "особенных" людей добавить в первый пост еще одно очевидное ограничение: "Предусмотреть переполнение".

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" 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 и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@cybercitizen 204 / 26 / 5 Регистрация: 22.05.2015 Сообщений: 357
	28.05.2015, 22:46 [ТС]
	Я прошу администрацию почистить тему от флуда. А для "особенных" людей добавить в первый пост еще одно очевидное ограничение: "Предусмотреть переполнение". 0