Найти строку матрицы с максимальной суммой элементов

Задача

В двумерном массиве (матрице) найти строку, сумма элементов которой является максимальной среди всех строк матрицы.

Решение

Решения данной задачи, когда требуется найти только одну строку с максимальной суммой элементов и когда таких строк несколько и все их надо определить, несколько различаются.

Рассмотрим сначала первый случай. Предположим, что в матрице суммы всех строк различны или для решения задачи достаточно найти первую с максимальной суммой.

Пусть переменная sum_max хранит найденную максимальную сумму. Переменная row_max хранит номер строки, элементы которой дают в сумме максимум.

Перебираем построчно матрицу. Перед вложенным циклом переменной sum (хранит сумму элементов текущей строки) присваиваем 0. Во вложенном цикле перебираются элементы текущей строки. Значение каждого из них добавляется к sum.

После того, как сумма элементов текущей строки посчитана (вышли из внутреннего цикла), проверяем не больше ли она значения, хранимого в sum_max. Если больше, то записываем ее в sum_max, а переменной row_max присваиваем номер текущей строки (хранится в переменной i).

В конце программы выводим значения sum_max и row_max (она содержит ответ задачи - номер искомой строки) на экран. В данном случае будет найдена только первая строка с максимальной суммой. Если бы в условном операторе использовался логический оператор >= (больше или равно), то, при наличии нескольких строк с максимальной суммой, была бы выведена на экран последняя.

const
    N = 5; M = 3; 
var
    a: array[1..N,1..M] of integer;
    i, j, row_max: byte;
    sum, sum_max: integer;
begin 
    randomize;
    for i:=1 to N do begin
        for j:=1 to M do begin
            a[i,j] := random(10);
            write(a[i,j]:3);
        end;
        writeln;
    end;
 
    sum_max := -1;
    row_max := 0;
    for i:=1 to N do begin
        sum := 0;
        for j:=1 to M do
            sum := sum + a[i,j];
        if sum > sum_max then begin
            sum_max := sum;
            row_max := i;
        end;        
    end;
 
    writeln('Строка ',row_max,', сумма ',sum_max);
end.

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

const
    N = 20; M = 3; 
var
    a: array[1..N,1..M] of integer;
    i, j: byte;
    sum, sum_max: integer;
begin 
    randomize;
    for i:=1 to N do begin
        for j:=1 to M do begin
            a[i,j] := random(10);
            write(a[i,j]:3);
        end;
        writeln;
    end;
 
    sum_max := -1;
    for i:=1 to N do begin
        sum := 0;
        for j:=1 to M do
            sum := sum + a[i,j];
        if sum > sum_max then 
            sum_max := sum;        
    end;
 
    write('Максимальную сумму ',sum_max,' содержат строки:');
    for i:=1 to N do begin
        sum := 0;
        for j:=1 to M do
            sum := sum + a[i,j];
        if sum = sum_max then 
            write(i:3);        
    end;
    writeln;
end.

Пример выполнения программы:

  7  8  6
  6  4  0
  1  8  1
  9  7  5
  4  3  0
  8  2  8
  4  7  0
  0  7  6
  1  5  9
  7  4  9
  0  3  3
  8  7  4
  5  5  1
  1  3  3
  8  8  4
  4  6  6
  8  1  6
  5  6  7
  8  9  4
  2  9  3
Максимальную сумму 21 содержат строки:  1  4 19

Тема

Матрицы

Уровень

Комбинированные задачи

Последняя редакция