Skip to main content

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).

Back to lesson: Practice: Debugging Problem Set