Условие

Дан массив целых чисел nums, найдите три числа, произведение которых максимально, и верните это произведение.

Примеры

Input: nums = [1, 2, 3] Output: 6

Input: nums = [1, 2, 3, 4] Output: 24

Input: nums = [-1, -2, -3] Output: -6

Решение

fun maximumProduct(nums: IntArray): Int {
    var max1 = Int.MIN_VALUE
    var max2 = Int.MIN_VALUE
    var max3 = Int.MIN_VALUE
    var min1 = Int.MAX_VALUE
    var min2 = Int.MAX_VALUE

    for (num in nums) {
        // Обновляем три наибольших числа
        when {
            num > max1 -> {
                max3 = max2
                max2 = max1
                max1 = num
            }
            num > max2 -> {
                max3 = max2
                max2 = num
            }
            num > max3 -> {
                max3 = num
            }
        }
        // Обновляем два наименьших числа
        when {
            num < min1 -> {
                min2 = min1
                min1 = num
            }
            num < min2 -> {
                min2 = num
            }
        }
    }
    // Максимальное произведение может быть между:
    // 1. Тремя наибольшими числами
    // 2. Двумя наименьшими (отрицательными) и одним наибольшим
    return maxOf(max1 * max2 * max3, min1 * min2 * max1)
}

Временная сложность

O(n), где n — длина массива, так как массив перебирается один раз.

Пространственная сложность

O(1), дополнительной памяти не используется.