Как найти наибольшее умножение между числами в заданном массиве (предел 100000 чисел)

Я пытаюсь изучать программирование, и в нашей школе есть упражнения, которые автоматически проверяются ботом. Ограничение по времени — 1 секунда, а ограничение по памяти — 1024 Мб. Я попытался отсортировать массив в порядке возрастания, а затем умножить 2 самых высоких числа, но это было слишком медленно (мой алгоритм сортировки может быть медленным, поэтому, если возможно, предложите алгоритм сортировки.) Это самый быстрый способ, который я смог сделать:

#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
int Maksimumas(int n, int X[]);
ofstream fr("U1rez.txt");
ifstream fd("U1.txt");
int main()
{
    int n, A[100000], B[100000], maxi=0;
    fd >> n;
    for (int i = 0; i < n; i++) {
        fd >> A[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            B[j] = A[i] * A[j];
        }
        maxi = Maksimumas(n, B);
        A[i] = B[maxi];
    }
    maxi = Maksimumas(n, A);
    fr << A[maxi];
    fr.close();
    return 0;
}
int Maksimumas(int n, int X[])
{
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        if (X[maxi] < X[i]) {
            maxi = i;
        }
    }
    return maxi;
}

n - размер массива для всех, кто интересуется.

Если вы хотите найти максимальное и второе максимальное число, вам действительно нужно сортировать весь массив?

Gaurav Sehgal 09.04.2022 17:19

Попробуйте использовать std::nth_element.

273K 09.04.2022 17:23

или std::partial_sort

463035818_is_not_a_number 09.04.2022 17:24

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

emirisu 09.04.2022 17:25

сортировка O(N * logN), в то время как для нахождения максимального и второго максимального числа необходим только один проход по массиву.

463035818_is_not_a_number 09.04.2022 17:27

Как бы вы предложили найти 2-й максимум, если предположить, что это может быть одно и то же число? Я не знаю, как решить такую ​​​​проблему

emirisu 09.04.2022 17:30

Я имею в виду, когда вы найдете новый максимум, что вы сможете сделать со старым максимумом?

sweenish 09.04.2022 18:25
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
2
7
32
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вам не нужно сортировать весь массив — вам просто нужны два самых больших положительных числа и два самых маленьких отрицательных числа. Все, что между ними, не имеет значения.

Вместо этого вы можете просмотреть весь ввод и отследить два самых больших положительных числа и два самых маленьких отрицательных числа.; В конце итерации умножьте каждую пару (если она найдена) и сравните результаты.

// fd is opened like the original question, n is the number of elements to read
// that part is omitted for brevity

int max = -1; 
int preMax = -1;
int min = 1;
int preMin = 1;

int temp;
for (int i = 0; i < n; i++) {
    fd >> temp;
    if (temp > preMax) {
        if (temp > max) {
            preMax = max;
            max = temp;
        } else {
            preMax = temp;
        }
    } else if (temp < preMin) {
        if (temp < min) {
            preMin = min;
            min = temp;
        } else {
            preMin = temp;
        }
    }
}

int result = -1;
if (preMax >= 0) {
    result = preMax * max;
}
if (preMin <= 0) {
    int tempResult = preMin * min;
    if (tempResult > result) {
        result = tempResult;
    }
}

return result; 

Вы находите как максимумы, так и минимумы, помещая числа в массив?

emirisu 09.04.2022 17:33

@emirisu нет, я не трачу память на массив - я просто отслеживаю два самых больших положительных и два самых маленьких отрицательных значения.

Mureinik 09.04.2022 17:33

Спасибо за помощь! У меня наконец-то получилось :). Мне все еще нужно было добавить некоторые команды if, чтобы код работал, если n меньше 4, и все же, если бы не ваше предложение, я, вероятно, не нашел бы решения.

emirisu 09.04.2022 19:34

Другие вопросы по теме