Clasa a X-a · Tablouri bidimensionale (matrice)Read in English

Linia cu suma maximă în C++

În engleză: Row with the maximum sum

O(n²)C++1760 de linii2 exemple

Ideea

Calculăm suma fiecărei linii și o comparăm cu cea mai mare sumă găsită până acum. Pornim maximul de la suma primei linii (nu de la 0, pentru că sumele pot fi negative). Comparația strictă > păstrează prima linie în caz de egalitate. Se afișează indicele liniei (de la 1) și suma.

Descrierea în engleză

We compute the sum of every row and compare it with the largest sum found so far. The maximum starts from the sum of the first row (not from 0, because sums can be negative). The strict comparison > keeps the first row on ties. The row index (from 1) and the sum are printed.

Complexitate
O(n * m)
Clasa
Clasa a X-a (Grade 10)

Exemple

Exemplul 1

Intrare

3 3
1 2 3
9 0 1
4 4 2

Ieșire așteptată

2 10
Exemplul 2

Intrare

2 2
-5 -1
-2 -3

Ieșire așteptată

2 -5

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

linia-cu-suma-maxima.cpp
/*
 * Titlu: Linia cu suma maximă
 * Clasa: 10
 * Capitol: Tablouri bidimensionale (matrice)
 * Descriere: Calculăm suma fiecărei linii și o comparăm cu cea mai mare sumă găsită
 *            până acum. Pornim maximul de la suma primei linii (nu de la 0, pentru
 *            că sumele pot fi negative). Comparația strictă > păstrează prima linie
 *            în caz de egalitate. Se afișează indicele liniei (de la 1) și suma.
 * Complexitate: O(n * m)
 *
 * Exemplu
 * Intrare:
 * 3 3
 * 1 2 3
 * 9 0 1
 * 4 4 2
 * Ieșire: 2 10
 *
 * Exemplu
 * Intrare:
 * 2 2
 * -5 -1
 * -2 -3
 * Ieșire: 2 -5
 */
#include <iostream>
using namespace std;

int a[101][101];

int sumaLinie(int i, int m)
{
    int s = 0;
    for (int j = 1; j <= m; j++)
        s += a[i][j];
    return s;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    int linieMax = 1, sumaMax = sumaLinie(1, m);
    for (int i = 2; i <= n; i++)
    {
        int s = sumaLinie(i, m);
        if (s > sumaMax)
        {
            sumaMax = s;
            linieMax = i;
        }
    }
    cout << linieMax << ' ' << sumaMax << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.