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

@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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .

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