Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

---

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout); định dạng xem ở mục Dữ liệu vào.

LeetCode 2025 – Maximum Number of Ways to Partition an Array (Số cách chia mảng nhiều nhất) – độ khó Hard.

Cho mảng số nguyên nums độ dài ~n~, đánh số từ 0. Số cách chia mảng nums là số lượng chỉ số pivot thỏa mãn đồng thời cả hai điều kiện:

• ~1 \le~ pivot ~\lt n~
• nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]

Ngoài ra cho số nguyên ~k~. Bạn có thể chọn đổi giá trị của một phần tử của nums thành ~k~, hoặc giữ nguyên mảng không đổi.

Yêu cầu: trả về số cách chia mảng nums thỏa mãn cả hai điều kiện trên lớn nhất có thể sau khi đổi tối đa một phần tử.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên ~n~ và ~k~.
• Dòng thứ hai gồm ~n~ số nguyên nums[0], nums[1], ..., nums[n-1].

Kết quả

• In ra một số nguyên là số cách chia mảng lớn nhất có thể.

Giới hạn

• n == nums.length
• ~2 \le n \le 10^5~
• ~-10^5 \le~ k, nums[i] ~\le 10^5~

Sample Input 1

3 3
2 -1 2

Sample Output 1

1

Giải thích

Một cách tối ưu là đổi nums[0] thành ~k~. Mảng trở thành [3,-1,2]. Có một cách chia mảng:

• Với pivot = 2, ta có cách chia [3,-1 | 2]: 3 + -1 == 2.

Sample Input 2

3 1
0 0 0

Sample Output 2

2

Giải thích

Cách tối ưu là giữ nguyên mảng. Có hai cách chia mảng:

• Với pivot = 1, ta có cách chia [0 | 0,0]: 0 == 0 + 0.
• Với pivot = 2, ta có cách chia [0,0 | 0]: 0 + 0 == 0.

Sample Input 3

13 -33
22 4 -25 -20 -15 15 -16 7 19 -10 0 -13 -14

Sample Output 3

4

Giải thích

Một cách tối ưu là đổi nums[2] thành ~k~. Mảng trở thành [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14]. Có bốn cách chia mảng.

Nguồn: LeetCode 2025.