how to find the biggest multiplication between numbers in a given array(limit is 100000 numbers)

user_18756354 0
Viewed 45

I am trying to learn programming and in our school we have exercises which are automatically checked by a bot. The time limit is 1 second and the memory limit is 1024 mb. I've tried sorting the array in an ascending order and then multiplicating the 2 highest numbers but that was too slow(my sorting algorithm could be slow so if possible suggest a sorting algorithm.) This is the fastest way that I've been able to do:

#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 is the size of the array for anyone wondering.

multiplication sorting arrays c++
1 Answers

You don't need to sort the entire array - you just need the two largest positive numbers and the two smallest negative numbers. Everything in between is inconsequential.

Instead, you can go over all the input and keep track of the two largest positive numbers and two smallest negative numbers.; At the end of the iteration, multiply each pair (if found), and compare the results.

// 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;
user_24227760
Related