1. Идея

Нужно обработать матрицу построчно и для каждой строки найти её максимальный элемент.

Так как требуется вывести по одному числу для каждой строки, естественный способ решения такой:

• читаем очередную строку;
• находим в ней максимум;
• сохраняем ответ;
• после обработки всех строк выводим найденные максимумы.

2. Наблюдения

1. Для одной строки ответ — это просто наибольший элемент среди c чисел.

2. Нет необходимости хранить всю матрицу целиком:

   • ответ для строки зависит только от элементов этой строки;
   • значит, можно обработать строку сразу после чтения.

3. Все элементы могут быть отрицательными, поэтому нельзя начинать максимум с 0. Нужно брать первым максимумом один из реальных элементов строки, например первый.

4. Ограничения r, c <= 1000 означают, что всего элементов не более 10^6. Полный проход по всем элементам работает быстро.

3. Алгоритм

Для каждой строки:

1. Считать элементы строки.
2. Взять первый элемент как текущий максимум.
3. Пройти по остальным элементам строки.
4. Если очередной элемент больше текущего максимума, обновить максимум.
5. Сохранить максимум этой строки в массив ответов.

После этого вывести все сохранённые максимумы через пробел.

4. Почему это работает

Рассмотрим одну фиксированную строку.

• В начале текущий максимум равен первому элементу строки.
• Затем мы последовательно просматриваем остальные элементы.
• После просмотра каждого элемента поддерживается верное утверждение: текущий максимум равен наибольшему из уже просмотренных элементов.
• Если новый элемент больше текущего максимума, мы заменяем максимум на него.
• Если не больше, максимум остаётся прежним.

После обработки всей строки текущий максимум будет равен наибольшему элементу всей строки.
Так делается для каждой из r строк, значит в ответе окажутся максимумы всех строк сверху вниз, как и требуется.

5. Сложность

Пусть в матрице r строк и c столбцов.

• Время: O(r * c), потому что каждый элемент матрицы просматривается ровно один раз.
• Память:
  • в C++: O(r) для массива ответов;
  • в Python по данному решению: O(c + r), потому что строка читается в список, а также хранится список ответов.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int r, c;
    cin >> r >> c;

    vector<long long> ans;
    ans.reserve(r);

    for (int i = 0; i < r; i++) {
        long long x;
        cin >> x;
        long long mx = x;

        for (int j = 1; j < c; j++) {
            cin >> x;
            if (x > mx) {
                mx = x;
            }
        }

        ans.push_back(mx);
    }

    for (int i = 0; i < r; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

r, c = map(int, input().split())

ans = []

for _ in range(r):
    row = list(map(int, input().split()))
    mx = row[0]
    for j in range(1, c):
        if row[j] > mx:
            mx = row[j]
    ans.append(mx)

print(*ans)