Решите задачу срочно!!! Даю 100 балов.
Задача №111176. Наибольшее произведение трех чисел
В данном списке из ≤105
n
≤
10
5
целых чисел найдите три числа,произведение которых максимально.
Решение должно иметь сложность ()
O
(
n
)
, где
n
- размер списка.
Выведите три искомых числа в любом порядке.
Примеры
входные данные
3 5 1 7 9 0 9 -3 10
выходные данные
10 9 9
входные данные
-5 -30000 -12
выходные данные
-5 -12 -30000
Ответы
#include <iostream>
#include <cmath>
using namespace std;
void solve(){
const long long INF = 1e10;
long long max1 = -INF, max2 = -INF, max3 = -INF, min1 = INF, min2 = INF, x = INF;
string s, cur;
getline(cin, s);
for(int i = 0; i <= s.length(); i++){
if(i == s.length() || s[i] == ' '){
x = stoll(cur);
if(x > max1){
max3 = max2;
max2 = max1;
max1 = x;
}
else if(x > max2){
max3 = max2;
max2 = x;
}
else if(x > max3){
max3 = x;
}
if(x < min1){
min2 = min1;
min1 = x;
}
else if(x < min2){
min2 = x;
}
cur.clear();
}
else{
cur += s[i];
}
}
if(max1 * max2 * max3 > max1 * min1 * min2)
cout << max3 << " " << max2 << " " << max1;
else
cout << min1 << " " << min2 << " " << max1;
}
int main() {
solve();
}
maxs = []
mins = []
for i in range(3):
if len(a) == 0:
break
maxs.append(max(a))
a.pop(a.index(maxs[-1]))
for i in range(3):
if len(a) == 0:
break
mins.append(min(a))
a.pop(a.index(mins[-1]))
if len(mins) < 2:
print(maxs[0], maxs[1], maxs[2])
else:
if abs(mins[0] + mins[1]) > maxs[1] + maxs[2]:
print(mins[0], mins[1],maxs[0])
else:
print(maxs[0], maxs[1],maxs[2])
maxs = []
mins = []
for i in range(3):
if len(a) == 0:
break
maxs.append(max(a))
a.pop(a.index(maxs[-1]))
for i in range(3):
if len(a) == 0:
break
mins.append(min(a))
a.pop(a.index(mins[-1]))
if len(mins) < 2:
print(maxs[0], maxs[1], maxs[2])
else:
if abs(mins[0] + mins[1]) > maxs[1] + maxs[2]:
print(mins[0], mins[1],maxs[0])
else:
print(maxs[0], maxs[1],maxs[2])
a = list(map(int,input().split()))
max1, max2, max3 = -1000000000000, -1000000000000, -1000000000000
min1, min2 = 1000000000000, 1000000000000
for i in a:
if i > max1:
max3 = max2
max2 = max1
max1 = i
elif i > max2:
max3 = max2
max2 = i
elif i > max3:
max3 = i
if i < min1:
min2 = min1
min1 = i
elif i < min2:
min2 = i
if max1 * max2 * max3 > max1 * min1 * min2:
print(max3, max2, max1)
else:
print(min1, min2, max1)
