Maximum Number of Ways to Partition an Array (LeetCode 2025)
Đề bài
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ử.
Ràng buộc:
n == nums.length- $2 \le n \le 10^5$
- $-10^5 \le$
k,nums[i]$\le 10^5$
Ví dụ 1:
Input: nums = [2,-1,2], k = 3
Output: 1Giả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.
Ví dụ 2:
Input: nums = [0,0,0], k = 1
Output: 2Giả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.
Ví dụ 3:
Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4Giả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.
2025. Maximum Number of Ways to Partition an Array – Hard.
You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:
1 <= pivot < nnums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.
Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.
Example 1:
Input: nums = [2,-1,2], k = 3
Output: 1
Explanation: One optimal approach is to change nums[0] to k. The array becomes [3,-1,2].
There is one way to partition the array:
- For pivot = 2, we have the partition [3,-1 | 2]: 3 + -1 == 2.Example 2:
Input: nums = [0,0,0], k = 1
Output: 2
Explanation: The optimal approach is to leave the array unchanged.
There are two ways to partition the array:
- For pivot = 1, we have the partition [0 | 0,0]: 0 == 0 + 0.
- For pivot = 2, we have the partition [0,0 | 0]: 0 + 0 == 0.Example 3:
Input: nums = [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k = -33
Output: 4
Explanation: One optimal approach is to change nums[2] to k. The array becomes [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14].
There are four ways to partition the array.Constraints:
n == nums.length2 <= n <= 10^5-10^5 <= k, nums[i] <= 10^5
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
class Solution. Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), mọi code trong bài đều có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 gồm hai số $n$ và $k$, dòng 2 gồm $n$ số của mảng nums; in ra một số nguyên là đáp án. Ví dụ 1 sẽ nhập là:3 3
2 -1 21.Tóm tắt đề bài: ta được cho một dãy số nguyên $a$ gồm $N$ số. Ta gọi số cách chia dãy làm 2 phần bằng nhau là số lượng vị trí pivot sao cho $a[1] + a[2] + \dots + a[pivot] = a[pivot + 1] + a[pivot + 2] + \dots + a[n]$ (trong bài mình đánh số từ 1 cho dễ viết). Bạn có quyền thay đổi một số $a[i]$ bất kỳ thành số $k$ (hoặc không đổi gì). Hãy chọn số cần đổi sao cho số lượng cách chia dãy thành 2 phần bằng nhau là lớn nhất có thể.
Ví dụ 1: [2, -1, 2], $k = 3$. Giữ nguyên thì: cắt sau phần tử 1 được $2$ và $-1 + 2 = 1$ – lệch; cắt sau phần tử 2 được $2 - 1 = 1$ và $2$ – lệch ⇒ 0 cách. Đổi $a[1] = 2$ thành $3$: mảng [3, -1, 2], cắt sau phần tử 2 được $3 - 1 = 2$ bằng $2$ ⇒ 1 cách. Thử hết các phương án thì không có cách nào được 2 ⇒ đáp án 1.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Thử đổi từng phần tử rồi đếm lại – O(n²)
Làm đúng theo đề: có $n + 1$ phương án (không đổi gì, hoặc đổi $a[i]$ thành $k$ với $i = 1..n$). Với mỗi phương án, ta đếm số pivot hợp lệ bằng một vòng for: duy trì tổng tiền tố $pre$, pivot hợp lệ khi $pre = total - pre$. Mỗi lần đếm mất $O(n)$.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// đếm số pivot chia dãy a thành 2 phần có tổng bằng nhau
int countWays(vector<int>& a) {
int n = (int) a.size();
long long total = 0, pre = 0;
for (int i = 0; i < n; i++) total += a[i];
int cnt = 0;
for (int p = 1; p < n; p++) {
pre += a[p - 1];
if (pre == total - pre) cnt++;
}
return cnt;
}
int waysToPartition(vector<int>& a, int k) {
int n = (int) a.size();
int ans = countWays(a); // không đổi phần tử nào
for (int i = 0; i < n; i++) {
int old = a[i];
a[i] = k; // thử đổi a[i] thành k
ans = max(ans, countWays(a));
a[i] = old; // trả lại như cũ
}
return ans;
}
};
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
Solution sol;
cout << sol.waysToPartition(a, k);
return 0;
}import sys
from typing import List
class Solution:
def countWays(self, a: List[int]) -> int:
# đếm số pivot chia dãy a thành 2 phần có tổng bằng nhau
total = sum(a)
pre = 0
cnt = 0
for p in range(1, len(a)):
pre += a[p - 1]
if pre == total - pre:
cnt += 1
return cnt
def waysToPartition(self, a: List[int], k: int) -> int:
ans = self.countWays(a) # không đổi phần tử nào
for i in range(len(a)):
old = a[i]
a[i] = k # thử đổi a[i] thành k
ans = max(ans, self.countWays(a))
a[i] = old # trả lại như cũ
return ans
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
print(Solution().waysToPartition(a, k))
main()Cách 2Mảng cộng dồn hai chiều + map – O(n log n)
Phương pháp giải: Duyệt + cấu trúc dữ liệu.
Đổi a[i] thì mỗi pivot thay đổi thế nào?
Trước hết, ta gọi $sum[i] = a[1] + a[2] + \dots + a[i]$ (tổng tiền tố) và $revSum[i] = a[n] + a[n - 1] + \dots + a[i]$ (tổng hậu tố). Ta có thể dễ dàng build 2 bảng này. Pivot $j$ ($1 \le j \lt n$) hợp lệ khi $sum[j] = revSum[j + 1]$. Để gọn, mình đặt
Khi ta thay đổi số $a[i]$ thành số $k$, ta nhận xét như sau:
- Với mọi vị trí $j \ge i$ (phần tử $a[i]$ nằm ở nửa trái): $sum[j]$ mới $= sum[j]$ cũ trừ $a[i]$ cộng thêm $k$, còn $revSum[j + 1]$ giữ nguyên. Do đó pivot $j$ hợp lệ khi $sum[j] - a[i] + k = revSum[j + 1] \iff d[j] = a[i] - k$.
- Với mọi vị trí $j \lt i$ (phần tử $a[i]$ nằm ở nửa phải): $revSum[j + 1]$ mới $= revSum[j + 1]$ cũ trừ $a[i]$ cộng thêm $k$. Do đó pivot $j$ hợp lệ khi $sum[j] = revSum[j + 1] - a[i] + k \iff d[j] = k - a[i]$.
Đáp án $= \max\big(\text{số } j \text{ có } d[j] = 0,\ \max_i (l[i] + r[i])\big)$.
Đếm l[i], r[i] bằng map
- Tính $r[i]$: gọi $cnt[v]$ là số lượng giá trị $d[j] = v$. Ta duyệt vòng for $i$ ngược từ $n - 1$ về $1$: tăng $cnt[d[i]]$ lên 1 đơn vị (để $j = i$ cũng được tính), rồi cộng vào $r[i]$ lượng $cnt[a[i] - k]$.
- Tính $l[i]$: làm lại $cnt$ từ đầu, duyệt vòng for $i$ từ $1$ tới $n$: cộng vào $l[i]$ lượng $cnt[k - a[i]]$ (lúc này $cnt$ chỉ chứa các $d[j]$ với $j \lt i$), rồi mới tăng $cnt[d[i]]$ lên 1 đơn vị.
Kết quả là giá trị lớn nhất của các tổng $l[i] + r[i]$ với mọi $i$ từ $1$ tới $n$ (và số cách khi không đổi gì).
map<long long, int>. Tổng tiền tố cũng vượt int nên phải khai báo long long.Minh hoạ: thử đổi từng a[i]
Em nhập mảng và $k$ rồi bấm Tiếp. Bảng tính sẵn $d[j]$ của từng pivot; khi xét đổi $a[i]$, cột xanh dương là các pivot $j \lt i$ (cần $d[j] = k - a[i]$), cột cam là các pivot $j \ge i$ (cần $d[j] = a[i] - k$), ô xanh lá là pivot khớp:
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:
#include <bits/stdc++.h>
using namespace std;
long long sum[100005], revSum[100005];
int l[100005], r[100005];
class Solution {
public:
int waysToPartition(vector<int>& a, int k) {
int ans = 0;
int n = (int) a.size();
memset(sum, 0, sizeof(sum));
memset(revSum, 0, sizeof(revSum));
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i - 1];
}
for (int i = n; i >= 1; i--) {
revSum[i] = revSum[i + 1] + a[i - 1];
}
int cnt = 0;
for (int i = 1; i < n; i++) {
if (sum[i] == revSum[i + 1]) {
cnt++;
}
}
ans = max(ans, cnt);
map <long long, int> M;
for (int i = 1; i <= n; i++) {
l[i] += M[k - a[i - 1]];
M[sum[i] - revSum[i + 1]]++;
}
M.clear();
for (int i = n - 1; i >= 1; i--) {
M[sum[i] - revSum[i + 1]]++;
r[i] += M[a[i - 1] - k];
}
for (int i = 1; i <= n; i++) {
ans = max(ans, l[i] + r[i]);
}
return ans;
}
};
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
Solution sol;
cout << sol.waysToPartition(a, k);
return 0;
}import sys
from typing import List
from collections import defaultdict
class Solution:
def waysToPartition(self, a: List[int], k: int) -> int:
n = len(a)
# đánh số từ 1 như bản C++: sum[i] = a[1] + ... + a[i], revSum[i] = a[i] + ... + a[n]
sum_ = [0] * (n + 2)
revSum = [0] * (n + 2)
for i in range(1, n + 1):
sum_[i] = sum_[i - 1] + a[i - 1]
for i in range(n, 0, -1):
revSum[i] = revSum[i + 1] + a[i - 1]
l = [0] * (n + 2)
r = [0] * (n + 2)
ans = 0
cnt = 0
for i in range(1, n):
if sum_[i] == revSum[i + 1]:
cnt += 1
ans = max(ans, cnt)
M = defaultdict(int)
for i in range(1, n + 1):
l[i] += M[k - a[i - 1]]
M[sum_[i] - revSum[i + 1]] += 1
M.clear()
for i in range(n - 1, 0, -1):
M[sum_[i] - revSum[i + 1]] += 1
r[i] += M[a[i - 1] - k]
for i in range(1, n + 1):
ans = max(ans, l[i] + r[i])
return ans
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]
print(Solution().waysToPartition(a, k))
main()Đánh giá độ phức tạp của cách làm này:
- Thời gian: build 2 mảng cộng dồn mất $O(n)$; hai vòng for dùng map, mỗi thao tác trên map mất $O(\log n)$ ⇒ tổng cộng $O(n \log n)$.
- Không gian: các mảng
sum,revSum,l,rvà map ⇒ $O(n)$.
revSum nếu muốn, ý tưởng vẫn y như trên. Nếu thay map bằng unordered_map thì độ phức tạp trung bình còn $O(n)$.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét