Алгоритм по поиску максимального произведения трех чисел

Question

Алгоритм по поиску максимального произведения трех чисел

Рейтинг: 1Ответов: 1Опубликовано: 29.07.2023

Надо найти максимальное произведение трех чисел из массива. Я написал код, но на одном из этапов проверки есть ошибка. Можете помочь, сказав где ошибка (не могу найти сам)

Мой код на python:

def max3(n, arr):
    max1 = 0
    max2 = 1
    max3 = 2

    t = 1
    while t:
        if ((arr[max1] <= arr[max2]) and (arr[max1] <= arr[max2]) and (arr[max1] <= arr[max2])):
            t = 0
            break
        if (arr[max1] > arr[max2]):
            max1, max2 = max2, max1
        if (arr[max2] > arr[max3]):
            max3, max2 = max2, max3

    min1 = max1
    min2 = max2

    for i in range(3, n):
        if arr[max3] <= arr[i]:
            max1 = max2
            max2 = max3
            max3 = i
        elif arr[max2] <= arr[i]:
            max1 = max2
            max2 = i
        elif arr[max1] <= arr[i]:
            max1 = i

        if (arr[min1] >= arr[i]):
            min2 = min1
            min1 = i
        elif (arr[min2] > arr[i]):
            min2 = i

    maxarr = arr[max1] * arr[max2] * arr[max3]
    minarr = arr[min1] * arr[min2] * arr[max3]

    if maxarr > minarr:
        print(maxarr)
    else:
        print(minarr)

if __name__ == "__main__":
    k = int(input())
    arr1 = input()
    nums = list(map(int, arr1.split(' ')))
    max3(k, nums)

python алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Алгоритм словами не описан, буду гадать. Можно предположить что после цикла while ожидается что значения возрастают: arr[max1] <= arr[max2] <= arr[max3]. Это ясно из анализа циклаfor. Проверим:

def max3(n, arr):
    max1 = 0
    max2 = 1
    max3 = 2

    t = 1
    while t:
        if ((arr[max1] <= arr[max2]) and (arr[max1] <= arr[max2]) and (arr[max1] <= arr[max2])):
            t = 0
            break
        if (arr[max1] > arr[max2]):
            max1, max2 = max2, max1
        if (arr[max2] > arr[max3]):
            max3, max2 = max2, max3

    print(arr[max1], arr[max2], arr[max3])


max3(3, [10, 20, 30])
max3(3, [10, 30, 20])
max3(3, [20, 10, 30])
max3(3, [20, 30, 10])
max3(3, [30, 10, 20])
max3(3, [30, 20, 10])

$ python test.py
10 20 30
10 30 20
10 20 30
20 30 10
10 20 30
10 20 30

В четырёх случаях сортировка удалась, в двух провалилась. Самый неприятный случай 20 30 10. Давайте сделаем из него "плохой" пример: 20 30 10 15. Неправильная сортировка приводит к тому что в первом if внутри for значения меняются так: было 20 30 10, стало 30 10 15 (я напечатал не индексы а соответствующие значения). Произведение уменьшилось с 6000 до 4500.

Хорошие новости: главная идея верная. Надо подобрать три положительных побольше или одно положительное побольше и два отрицательных поменьше. Нужно уметь искать три максимума и два минимума.

Для поиска трёх максимумов будем поддерживать упорядоченный список из не более чем трёх элементов. Первоначально список пустой, новые элементы вставляются так чтобы порядок сохранялся. Если после вставки элементов больше трёх, первый (минимальный) удаляется:

def insert(a, v):
    a.append(v)
    for i in reversed(range(len(a) - 1)):
        if a[i] <= a[i + 1]:
            break
        a[i], a[i + 1] = a[i + 1], a[i]


def get_max3(a):
    max3 = []
    for v in a:
        insert(max3, v)
        if len(max3) > 3:
            max3.pop(0)
    return max3


def get_min2(a):
    min2 = []
    for v in a:
        insert(min2, v)
        if len(min2) > 2:
            min2.pop()
    return min2


def main():
    input() # skip n
    a = tuple(map(int, input().split()))
    max3 = get_max3(a)
    min2 = get_min2(a)
    print(max(
        max3[0] * max3[1] * max3[2],
        max3[2] * min2[0] * min2[1]
    ))


main()

P.S. get_max3 и get_min2 через sorted:

def get_max3(a):
    max3 = []
    for v in a:
        max3 = sorted(max3 + [v])[-3:]
    return max3


def get_min2(a):
    min2 = []
    for v in a:
        min2 = sorted(min2 + [v])[:2]
    return min2

P.P.S. Встроенный модуль heapq умеет делать всё из коробки - heapq.nlargest, heapq.nsmallest:

import heapq


input() # skip n
a = tuple(map(int, input().split()))
max3 = heapq.nlargest(3, a)
min2 = heapq.nsmallest(2, a)
print(max(
    max3[0] * max3[1] * max3[2],
    max(max3) * min2[0] * min2[1]
))

Алгоритм по поиску максимального произведения трех чисел

Ответы