Clasa a X-a · Tablouri bidimensionale (matrice)Read in English
Linia cu suma maximă în C++
În engleză: Row with the maximum sum
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
Intrare
3 3 1 2 3 9 0 1 4 4 2
Ieșire așteptată
2 10
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.
/*
* 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.