Practice · 3 of 5
Debug: Tham lam sai hướng
CHALLENGE
Difficulty: intermediate+25 XP
**Bài toán (đã đúng):** Có n đồng xu (giá trị có thể ÂM). Chọn một TẬP
CON KHÔNG RỖNG sao cho tổng lớn nhất; in tổng đó.
Phân tích đúng: chọn phần tử BẤT KỲ (không cần liên tiếp) → chọn mọi
phần tử dương; nếu không có phần tử dương nào, chọn đúng MỘT phần tử
lớn nhất (bắt buộc khác rỗng).
**Bản thảo sai:** quét LIÊN TIẾP (Kadane) với init best = 0 — liên
tiếp bỏ cơ hội nhảy qua đoạn âm lớn, và init 0 sai khi mọi xu âm.
**Yêu cầu:** viết bản đúng, pass mọi test.
**Input:** n; n giá trị (|a[i]| ≤ 10^4, n ≤ 2·10^5).
**Output:** tổng lớn nhất của tập con không rỗng.
**Ví dụ:** 4 / 2 -5 3 1 -> 6 (2+3+1; bỏ −5).
Press Submit to check your solution.
Back to lesson: Practice: Debugging Problem Set