PrepBro
← Назад к вопросам

Максимальная сумма в массиве

1.0 Junior🔥 141 комментариев
#Коллекции и структуры данных#Язык Swift

Условие

Дан двумерный массив целых чисел размера M x N. Найдите строку с максимальной суммой элементов и верните эту сумму.

Примеры:

Пример 1:

Вход: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Выход: 24
Объяснение: Строка [7, 8, 9] имеет максимальную сумму 7+8+9=24

Пример 2:

Вход: [[10, -5, 3], [1, 2, 3], [-1, -2, -3]]
Выход: 8
Объяснение: Строка [10, -5, 3] имеет максимальную сумму 10-5+3=8

Требования:

  • Временная сложность: O(M * N)
  • Пространственная сложность: O(1) (не считая входного массива)

Бонус: Решите задачу с использованием функций высшего порядка Swift (map, reduce).

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Основное решение O(M*N) время, O(1) память

func maxRowSum(_ matrix: [[Int]]) -> Int {
    guard !matrix.isEmpty else { return 0 }
    
    var maxSum = Int.min
    
    for row in matrix {
        let rowSum = row.reduce(0, +)
        maxSum = max(maxSum, rowSum)
    }
    
    return maxSum
}

Как это работает:

  1. Проходим по каждой строке матрицы - O(M)
  2. Для каждой строки вычисляем сумму элементов - O(N)
  3. Отслеживаем максимальную сумму
  4. Общая сложность: O(M*N)

Решение с использованием map и reduce

func maxRowSumFunctional(_ matrix: [[Int]]) -> Int {
    return matrix
        .map { $0.reduce(0, +) }  // Преобразуем каждую строку в её сумму
        .max() ?? Int.min         // Находим максимум
}

Поток выполнения:

  1. map { $0.reduce(0, +) } - преобразует каждый массив в сумму его элементов
  2. .max() - находит максимальное значение
  3. ?? Int.min - обработка пустого массива

Решение с явным циклом (более явное)

func maxRowSumExplicit(_ matrix: [[Int]]) -> Int {
    var maxSum = Int.min
    
    for row in matrix {
        var rowSum = 0
        for element in row {
            rowSum += element
        }
        maxSum = max(maxSum, rowSum)
    }
    
    return maxSum
}

Тестирование

let test1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(maxRowSum(test1))  // 24
print(maxRowSumFunctional(test1))  // 24

let test2 = [[10, -5, 3], [1, 2, 3], [-1, -2, -3]]
print(maxRowSum(test2))  // 8
print(maxRowSumFunctional(test2))  // 8

// Граничные случаи
let test3: [[Int]] = []  // Пустая матрица
print(maxRowSum(test3))  // Int.min

let test4 = [[-1, -2, -3]]  // Все отрицательные
print(maxRowSum(test4))  // -6

let test5 = [[100]]  // Одно число
print(maxRowSum(test5))  // 100

Анализ

Временная сложность: O(M*N)

  • M итераций по строкам
  • N итераций по элементам в каждой строке
  • Каждый элемент посещается ровно один раз

Пространственная сложность: O(1)

  • Используем только переменные maxSum и rowSum
  • Не создаём дополнительные структуры данных

Рекомендация

Для интервью используйте функциональный подход - это показывает знание Swift и функционального программирования:

func maxRowSum(_ matrix: [[Int]]) -> Int {
    return matrix.map { $0.reduce(0, +) }.max() ?? Int.min
}
Максимальная сумма в массиве | PrepBro