Dòng có tổng lớn nhất

Nguồn: CLUE OJ Độ khó: Dễ Mảng 2 chiều Tìm max

Đề bài

Cho mảng hai chiều $a$ gồm $m$ dòng và $n$ cột. Hãy tìm dòng có tổng các phần tử lớn nhất và in ra tổng lớn nhất đó.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương $m, n$.
• $m$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên là một dòng của mảng $a$.

Kết quả:

In ra một số nguyên là tổng lớn nhất trong các tổng của từng dòng.

Giới hạn:

• $1 \le m, n \le 500$
• $|a[i][j]| \le 10^9$ (các phần tử có thể âm)

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ 1 – input

3 4
3 1 5 2
3 6 1 2
1 2 3 4

Ví dụ 1 – output

12

Tổng ba dòng lần lượt là $3 + 1 + 5 + 2 = 11$, $3 + 6 + 1 + 2 = 12$ và $1 + 2 + 3 + 4 = 10$. Tổng lớn nhất là $12$.

Nguồn: phỏng theo bài "MỞ RỘNG TH3" – vinhdinhcoder.net (chủ đề Mảng 2 chiều).

Lời mở đầu

Kết hợp hai kỹ thuật quen thuộc: tính tổng một dòng và tìm giá trị lớn nhất. Hai cái bẫy lớn: tổng một dòng có thể vượt int, và mọi dòng đều có thể có tổng âm. Ghi chú: đề gốc dùng tệp và chưa có giới hạn giá trị; trên CLUE OJ đọc bàn phím, mình bổ sung $|a[i][j]| \le 10^9$ (có số âm).

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngtổng từng dòng + maxLời giảicode C++ / PythonCái bẫycách làm saiTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 20 test, mỗi test đúng được 1 phần điểm như nhau. Mọi test có $1 \le m, n \le 500$, $|a[i][j]| \le 10^9$.

Test	Nội dung kiểm tra
1	Ví dụ của đề
2, 5, 9, 13, 18–19	Mọi dòng đều có tổng âm – khởi tạo max = 0 sẽ in sai 0
9, 11–15, 17–18	Tổng một dòng vượt $2^{31}$ (tới $5 \cdot 10^{11}$) – cộng bằng int bị tràn
3–4, 6–8, 10, 16, 20	Một dòng, một cột, các dòng bằng nhau, dòng lớn nhất ở cuối ma trận...

Ý tưởngMỗi dòng tính tổng riêng, so với kỷ lục

Với mỗi dòng i: đặt tong = 0, cộng các a[i][j] của dòng đó. Sau khi có tổng dòng, so sánh với kỷ lục best.

Kỷ lục ban đầu

Không được đặt best = 0 từ đầu: nếu mọi dòng có tổng âm, đáp án đúng là số âm nhưng best vẫn đứng ở 0. Cách an toàn: lấy tổng của dòng đầu tiên làm kỷ lục (điều kiện i == 0 || tong > best).

Tổng một dòng có thể tới $500 \cdot 10^9 = 5 \cdot 10^{11}$, vượt int (khoảng $2{,}1 \cdot 10^9$), nên dùng long long.

Em nhập ma trận (các dòng cách nhau bởi dấu ;) rồi bấm Tiếp:

Ma trận =

Ví dụ nhanh:

Lời giảiTổng từng dòng và kỷ lục

tong khai báo bên trong vòng lặp dòng nên tự về 0 ở mỗi dòng mới.

C++▶ Chạy tay từng dòng codeTính tổng mỗi dòng rồi cập nhật best.

Dữ liệu vào (stdin) – sửa thoải mái3 4 3 1 5 2 3 6 1 2 1 2 3 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Điều kiện i == 0 || tong > best: với dòng 0 luôn gán, các dòng sau chỉ gán khi lớn hơn.
2. Có thể thay bằng cách khởi tạo best = -9e18 (rất nhỏ), nhưng lấy dòng đầu làm mốc thì không phải đoán "số đủ nhỏ".
3. Python không bị tràn số nên không cần lo kiểu dữ liệu.

Không gian$O(m \cdot n)$

Thời gian$O(m \cdot n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.042s. Bản Python đúng 20/20 test, chạy lâu nhất 0.099s. Full điểm.

Cái bẫyNhững cách làm sai hay gặp

Các cách làm sai mình đã chấm thử trên bộ test:

Cách làm sai	Đúng	Ghi chú
Cộng tổng bằng int	12/20	sai test 9, 11, 12, 13, 14, 15, 17, 18
Khởi tạo best = 0	14/20	sai test 2, 5, 9, 13, 18, 19
Tính nhầm tổng theo cột	2/20	sai test 1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Quên đặt lại tong = 0 ở mỗi dòng	3/20	sai test 1, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
Lời giải chuẩn	C++	20/20	0.042s	Full điểm
	Python	20/20	0.099s	Full điểm
Tổng kiểu int	C++	12/20	–	Mất 8 test
best = 0	C++	14/20	–	Mất 6 test
Tổng theo cột	C++	2/20	–	Mất 18 test
Quên reset tổng	C++	3/20	–	Mất 17 test

Ghi chú của mình: khi tìm max/min, giá trị khởi tạo phải là một giá trị thật trong dữ liệu (phần tử/dòng đầu tiên) – đừng đoán bằng 0.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇