Условие

Дан массив из 2n целых чисел. Требуется разделить его на n пар, таких что сумма минимальных значений каждой пары максимальна. Верните эту максимальную сумму.

Примеры

Input: nums = [1, 4, 3, 2] Output: 4 Explanation: Оптимальное разбиение на пары: (1, 2) и (3, 4). Минимальные значения пар: 1 и 3. Их сумма равна 4.

Input: nums = [6, 2, 6, 5, 1, 2] Output: 9 Explanation: Оптимальное разбиение на пары: (1, 2), (2, 5), (6, 6). Минимальные значения пар: 1, 2 и 6. Их сумма равна 9.

Решение

fun arrayPairSum(nums: IntArray): Int {
    // Реализуем сортировку пузырьком
    for (i in nums.indices) {
        // Проходим по массиву до (size - i - 1), так как последние элементы уже отсортированы
        for (j in 0 until nums.size - i - 1) {
            // Если текущий элемент больше следующего, меняем их местами
            if (nums[j] > nums[j + 1]) {
                val temp = nums[j]
                nums[j] = nums[j + 1]
                nums[j + 1] = temp
            }
        }
    }

    var maxSum = 0

    // Проходим по отсортированному массиву с шагом 2
    for (i in nums.indices step 2) {
        // Суммируем минимальные значения каждой пары (каждый второй элемент)
        maxSum += nums[i]
    }

    // Возвращаем максимальную сумму
    return maxSum
}

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

O(n²) — Используем сортировку пузырьком, которая имеет сложность O(n²).

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

O(1) — Используется дополнительная память только для переменной суммы и временной переменной при сортировке.