Linia cu suma maximă într-o matrice C++

O sumă pe linie folosește toate coloanele unei singure linii. Un maxim între aceste sume cere două niveluri de lucru: calcularea sumei curente și compararea ei cu cel mai bun rezultat. Amestecarea nivelurilor este una dintre cauzele frecvente ale rezultatelor greșite la matrice.

Datele problemei

Citim 1 ≤ n,m ≤ 100 și o matrice cu n linii și m coloane. Valorile au modulul cel mult 10^9. Afișăm numărul liniei cu suma maximă, de la 1, și suma. Dacă mai multe linii au aceeași sumă maximă, o alegem pe prima.

Matricea clasică rezervă 100×100 celule. Dimensiunea logică este n×m. Nu presupunem că n=m: limita buclei pentru coloane este m, chiar dacă exemplul pe care îl testezi întâmplător este pătratic.

Liniile -5,-1,2; 3,-2,4; 1,1,1 au sumele -4,5,3. A doua linie câștigă.Mărește schema ↗

Exemplu calculat

Pentru liniile -5 -1 2, 3 -2 4, 1 1 1, sumele sunt -4, 5 și 3. Rezultatul este 2 5. Suma curentă se resetează la zero înaintea fiecărei linii, altfel a doua sumă ar include și prima linie.

Comparația cu best are loc după terminarea liniei. O sumă parțială mare nu garantează o sumă finală mare dacă urmează valori negative. Pentru 9 -20, valoarea 9 nu este suma liniei, care este -11.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    long long a[100][100];
    for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) cin >> a[i][j];
    long long best = 0; int linie = 0;
    for (int i=0; i<n; ++i) {
        long long suma = 0;
        for (int j=0; j<m; ++j) suma += a[i][j];
        if (i==0 || suma > best) { best=suma; linie=i; }
    }
    cout << linie+1 << ' ' << best << '\n';
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<vector<long long>> a(n, vector<long long>(m));
    for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) cin >> a[i][j];
    long long best = 0; int linie = 0;
    for (int i=0; i<n; ++i) {
        long long suma = 0;
        for (int j=0; j<m; ++j) suma += a[i][j];
        if (i==0 || suma > best) { best=suma; linie=i; }
    }
    cout << linie+1 << ' ' << best << '\n';
}

Inițializare și departajare

Condiția i==0 acceptă obligatoriu suma primei linii. Astfel best=0 este doar o valoare temporară, care nu concurează cu sumele reale. Dacă toate sumele sunt negative, rezultatul rămâne corect. Indicatorul linie păstrează indicele intern și este convertit în poziție de la 1 doar la afișare.

Folosim comparația strictă suma > best, pentru a păstra prima linie în caz de egalitate. Dacă enunțul cere toate liniile maxime, trebuie fie să le reții, fie să faci o a doua parcurgere după stabilirea sumei maxime.

Timpul este O(n·m), iar memoria datelor O(n·m). Dacă ai nevoie exclusiv de acest rezultat, poți aduna fiecare linie chiar la citire, fără să păstrezi matricea. Aici o memorăm pentru a face explicită diferența dintre reprezentare și parcurgere.

Exersează

Pentru matricea cu două linii -4 -3 și -2 -1, răspunsul este 2 -3. Pentru 1 2 și 2 1, răspunsul este 1 3. Verifică separat cazul cu o singură linie și cazul cu o singură coloană.

Adaptează cerința la coloana cu suma maximă: schimbă ordinea buclelor și variabila folosită la afișare. Explică de ce rezultatul pentru linii nu poate fi reutilizat direct pentru coloane.

Continuă cu citirea și transpunerea matricelor, maxime cu valori negative și sume pe dreptunghiuri.

Întrebări frecvente

Cum găsesc linia cu suma maximă dintr-o matrice?

Calculează separat suma fiecărei linii, apoi compar-o cu maximul curent. Resetează suma înainte de fiecare linie și păstrează atât valoarea maximă, cât și indicele liniei alese.

Cu ce inițializez maximul dacă matricea conține numere negative?

Cu suma unei linii existente, de exemplu prima. Inițializarea cu zero poate produce un maxim care nu aparține niciunei linii atunci când toate sumele sunt negative.

Ce linie aleg dacă două sume maxime sunt egale?

Lecția cere prima linie. Păstrează rezultatul anterior la egalitate și actualizează numai pentru o sumă strict mai mare. La afișare, transformă indicele intern de la zero în poziție de la unu.