Bài 7.4. Monotonic Stack/Queue và ứng dụng cơ bản
Bài 7.4. Monotonic Stack/Queue và ứng dụng cơ bản
Trong hành trình khám phá Cấu trúc dữ liệu và Giải thuật, chúng ta thường gặp phải những bài toán yêu cầu tìm kiếm các phần tử có mối quan hệ đặc biệt với nhau, ví dụ như phần tử lớn hơn/nhỏ hơn gần nhất bên trái/phải. Những bài toán này thoạt nhìn có vẻ cần duyệt qua nhiều phần tử, dẫn đến độ phức tạp O(N^2). Tuy nhiên, với sự trợ giúp của hai công cụ đặc biệt là Monotonic Stack và Monotonic Queue, chúng ta có thể giải quyết chúng một cách cực kỳ hiệu quả chỉ trong độ phức tạp O(N).
Bài viết này sẽ đi sâu vào khái niệm Monotonic Stack và Monotonic Queue, giải thích cách chúng hoạt động và minh họa bằng các ứng dụng cơ bản nhất với ngôn ngữ C++.
Monotonic Stack (Ngăn xếp Đơn điệu)
Khái niệm
Monotonic Stack (Ngăn xếp Đơn điệu) là một biến thể của cấu trúc dữ liệu Stack thông thường, nhưng nó duy trì một trật tự đơn điệu cho các phần tử bên trong nó. Điều này có nghĩa là các phần tử trong stack luôn được sắp xếp theo thứ tự tăng dần (Monotonically Increasing Stack) hoặc giảm dần (Monotonically Decreasing Stack) từ đáy lên đỉnh.
Mục đích chính của Monotonic Stack là giúp chúng ta tìm kiếm hiệu quả các phần tử lân cận (bên trái hoặc bên phải) thỏa mãn một điều kiện so sánh nhất định (lớn hơn hoặc nhỏ hơn phần tử hiện tại).
Cách hoạt động
Nguyên lý hoạt động cơ bản của Monotonic Stack khi xử lý một dãy số là: khi duyệt qua từng phần tử, chúng ta so sánh phần tử hiện tại với phần tử ở đỉnh stack. Dựa vào việc chúng ta muốn duy trì stack tăng dần hay giảm dần, chúng ta sẽ thực hiện hành động "pop" (bỏ phần tử ở đỉnh) cho đến khi thuộc tính đơn điệu được thỏa mãn trước khi "push" (thêm) phần tử hiện tại vào stack.
Điều kỳ diệu xảy ra khi chúng ta "pop" một phần tử: phần tử đang được xét chính là phần tử đầu tiên (bên phải hoặc bên trái, tùy hướng duyệt) thỏa mãn điều kiện so sánh (lớn hơn hoặc nhỏ hơn) đối với các phần tử vừa bị pop.
Ứng dụng cơ bản 1: Tìm phần tử lớn hơn tiếp theo (Next Greater Element - NGE)
Bài toán: Cho một mảng các số arr, tìm với mỗi phần tử arr[i], phần tử đầu tiên xuất hiện sau nó (bên phải) trong mảng mà lớn hơn arr[i]. Nếu không có phần tử nào như vậy, kết quả là -1.
Ví dụ: arr = [4, 5, 2, 10, 8]
Kết quả mong muốn: [5, 10, 10, -1, -1]
Giải pháp với Monotonic Stack:
Chúng ta sẽ sử dụng một Monotonically Decreasing Stack (stack giảm dần) để lưu trữ các chỉ số của các phần tử mà chúng ta chưa tìm thấy NGE của chúng. Khi duyệt qua mảng từ trái sang phải, nếu phần tử hiện tại arr[i] lớn hơn phần tử được tham chiếu bởi chỉ số ở đỉnh stack (arr[stack.top()]), điều đó có nghĩa là arr[i] chính là NGE cho arr[stack.top()]. Chúng ta sẽ pop chỉ số này ra khỏi stack và ghi nhận kết quả, sau đó lặp lại quá trình so sánh với đỉnh stack mới cho đến khi điều kiện đơn điệu được phục hồi hoặc stack rỗng. Cuối cùng, chúng ta push chỉ số i hiện tại vào stack.
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm> // Dùng cho std::fill nếu cần, hoặc khởi tạo trực tiếp
int main() {
std::vector<int> arr = {4, 5, 2, 10, 8};
int n = arr.size();
std::vector<int> nextGreater(n, -1); // Mảng lưu kết quả, khởi tạo với -1
std::stack<int> s; // Stack lưu trữ chỉ số
// Duyệt mảng từ trái sang phải
for (int i = 0; i < n; ++i) {
// Trong khi stack không rỗng VÀ phần tử tại chỉ số đỉnh stack nhỏ hơn phần tử hiện tại
// (Tức là phần tử hiện tại chính là NGE cho phần tử ở đỉnh stack)
while (!s.empty() && arr[s.top()] < arr[i]) {
// Phần tử tại chỉ số s.top() đã tìm thấy NGE của nó là arr[i]
nextGreater[s.top()] = arr[i];
// Pop chỉ số này ra vì đã xử lý xong
s.pop();
}
// Push chỉ số hiện tại vào stack.
// arr[i] lớn hơn tất cả các phần tử vừa bị pop, và nó sẽ là một ứng cử viên cho NGE
// của các phần tử sắp tới ở bên phải nó.
s.push(i);
}
// Các chỉ số còn lại trong stack không có phần tử nào lớn hơn ở bên phải
// Kết quả của chúng vẫn là -1 (đã được khởi tạo ban đầu)
// In kết quả
std::cout << "Original Array: ";
for (int x : arr) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "Next Greater Element: ";
for (int res : nextGreater) {
std::cout << res << " ";
}
std::cout << std::endl;
return 0;
}
Giải thích code:
- Chúng ta sử dụng
std::vector<int> nextGreater(n, -1)để lưu kết quả. Kích thước bằng kích thước mảng đầu vào và tất cả các giá trị được khởi tạo là -1. std::stack<int> s;là stack chính, nó lưu trữ chỉ số của các phần tử.- Vòng lặp
for (int i = 0; i < n; ++i)duyệt qua mảng từ trái sang phải. - Bên trong vòng lặp,
while (!s.empty() && arr[s.top()] < arr[i])là logic cốt lõi. Nó kiểm tra xem stack có rỗng không và liệu phần tử tại chỉ số ở đỉnh stack (arr[s.top()]) có nhỏ hơn phần tử hiện tại (arr[i]) không.- Nếu điều kiện này đúng, tức là
arr[i]là phần tử đầu tiên lớn hơnarr[s.top()]mà chúng ta gặp khi duyệt từ trái sang phải. Do đó,arr[i]chính là NGE củaarr[s.top()]. - Chúng ta gán
nextGreater[s.top()] = arr[i];để lưu kết quả. - Sau đó,
s.pop();loại bỏ chỉ sốs.top()ra khỏi stack vì chúng ta đã tìm thấy NGE cho nó. - Vòng
whiletiếp tục chạy, xử lý tất cả các phần tử còn lại trong stack mà nhỏ hơnarr[i]. Điều này đảm bảo stack luôn giảm dần về các giá trị (arr[index]).
- Nếu điều kiện này đúng, tức là
- Sau khi vòng
whilekết thúc, điều đó có nghĩa là hoặc stack rỗng, hoặc phần tử tại đỉnh stack lớn hơn hoặc bằngarr[i]. Lúc này,arr[i]chưa tìm thấy NGE của nó (nó có thể là NGE cho các phần tử sau này), nên chúng ta push chỉ sốicủa nó vào stack:s.push(i);. - Khi vòng lặp
forkết thúc, bất kỳ chỉ số nào còn lại trong stack đều không có phần tử nào lớn hơn ở bên phải của chúng, và kết quả của chúng vẫn là -1 như đã khởi tạo.
Độ phức tạp:
- Thời gian: O(N). Mỗi phần tử trong mảng được push vào stack tối đa một lần và pop ra khỏi stack tối đa một lần. Mọi thao tác stack (
push,pop,top,empty) đều là O(1). Do đó, tổng thời gian là tuyến tính theo kích thước mảng. - Không gian: O(N) trong trường hợp xấu nhất (ví dụ: mảng được sắp xếp giảm dần), khi tất cả các phần tử đều được push vào stack và chỉ pop ra ở cuối.
Ứng dụng cơ bản 2: Tìm phần tử nhỏ hơn tiếp theo (Next Smaller Element - NSE)
Bài toán: Cho một mảng các số arr, tìm với mỗi phần tử arr[i], phần tử đầu tiên xuất hiện sau nó (bên phải) trong mảng mà nhỏ hơn arr[i]. Nếu không có phần tử nào như vậy, kết quả là -1.
Ví dụ: arr = [4, 5, 2, 10, 8]
Kết quả mong muốn: [2, 2, -1, 8, -1]
Giải pháp với Monotonic Stack:
Bài toán này tương tự như NGE, nhưng thay vì tìm phần tử lớn hơn, chúng ta tìm phần tử nhỏ hơn. Do đó, chúng ta sẽ sử dụng một Monotonically Increasing Stack (stack tăng dần).
Khi duyệt qua mảng từ trái sang phải, nếu phần tử hiện tại arr[i] nhỏ hơn phần tử được tham chiếu bởi chỉ số ở đỉnh stack (arr[stack.top()]), điều đó có nghĩa là arr[i] chính là NSE cho arr[stack.top()]. Chúng ta pop chỉ số này và ghi nhận kết quả, lặp lại cho đến khi điều kiện đơn điệu được thỏa mãn hoặc stack rỗng. Cuối cùng, push chỉ số i vào stack.
#include <iostream>
#include <vector>
#include <stack>
int main() {
std::vector<int> arr = {4, 5, 2, 10, 8};
int n = arr.size();
std::vector<int> nextSmaller(n, -1); // Mảng lưu kết quả, khởi tạo với -1
std::stack<int> s; // Stack lưu trữ chỉ số
// Duyệt mảng từ trái sang phải
for (int i = 0; i < n; ++i) {
// Trong khi stack không rỗng VÀ phần tử tại chỉ số đỉnh stack lớn hơn phần tử hiện tại
// (Tức là phần tử hiện tại chính là NSE cho phần tử ở đỉnh stack)
while (!s.empty() && arr[s.top()] > arr[i]) {
// Phần tử tại chỉ số s.top() đã tìm thấy NSE của nó là arr[i]
nextSmaller[s.top()] = arr[i];
// Pop chỉ số này ra vì đã xử lý xong
s.pop();
}
// Push chỉ số hiện tại vào stack.
// arr[i] nhỏ hơn tất cả các phần tử vừa bị pop, và nó sẽ là một ứng cử viên cho NSE
// của các phần tử sắp tới ở bên phải nó.
s.push(i);
}
// Các chỉ số còn lại trong stack không có phần tử nào nhỏ hơn ở bên phải
// Kết quả của chúng vẫn là -1 (đã được khởi tạo ban đầu)
// In kết quả
std::cout << "Original Array: ";
for (int x : arr) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "Next Smaller Element: ";
for (int res : nextSmaller) {
std::cout << res << " ";
}
std::cout << std::endl;
return 0;
}
Giải thích code:
Cấu trúc code và logic tương tự như NGE, điểm khác biệt chính nằm ở điều kiện trong vòng while: arr[s.top()] > arr[i]. Chúng ta pop khi phần tử ở đỉnh stack lớn hơn phần tử hiện tại arr[i], vì arr[i] lúc này đóng vai trò là NSE cho các phần tử đó. Stack lúc này duy trì thuộc tính tăng dần về giá trị (arr[index]).
Độ phức tạp:
- Thời gian: O(N). Mỗi phần tử được push/pop tối đa một lần.
- Không gian: O(N) trong trường hợp xấu nhất (e.g., mảng sắp xếp tăng dần).
Các biến thể khác
Với cùng nguyên lý này, chúng ta có thể dễ dàng giải các bài toán:
- Previous Greater Element (PGE): Tìm phần tử lớn hơn đầu tiên bên trái. Duyệt mảng từ phải sang trái, dùng Monotonically Decreasing Stack.
- Previous Smaller Element (PSE): Tìm phần tử nhỏ hơn đầu tiên bên trái. Duyệt mảng từ phải sang trái, dùng Monotonically Increasing Stack.
Monotonic Stack là một kỹ thuật cực kỳ hiệu quả để tìm kiếm các phần tử lân cận thỏa mãn điều kiện so sánh trong mảng hoặc danh sách.
Monotonic Queue (Hàng đợi Đơn điệu)
Khái niệm
Monotonic Queue (Hàng đợi Đơn điệu), thường được cài đặt bằng std::deque trong C++, là một cấu trúc dữ liệu duy trì trật tự đơn điệu cho các phần tử của nó, tương tự như Monotonic Stack. Tuy nhiên, điểm mạnh của Monotonic Queue nằm ở khả năng thêm và xóa phần tử ở cả hai đầu một cách hiệu quả (O(1)).
Monotonic Queue lý tưởng để giải quyết các bài toán liên quan đến cửa sổ trượt (sliding window), đặc biệt là khi cần tìm giá trị lớn nhất hoặc nhỏ nhất trong cửa sổ đó một cách nhanh chóng.
Cách hoạt động
Khi sử dụng Monotonic Queue cho bài toán cửa sổ trượt, chúng ta sẽ duy trì một hàng đợi (deque) các phần tử (thường là chỉ số của chúng) sao cho chúng có thứ tự đơn điệu. Khi cửa sổ trượt sang phải, chúng ta thêm phần tử mới vào cửa sổ (và vào deque) và loại bỏ phần tử cũ ra khỏi cửa sổ (và có thể loại bỏ khỏi deque nếu nó nằm ở đầu deque). Đồng thời, chúng ta duy trì thuộc tính đơn điệu của deque bằng cách loại bỏ các phần tử ở cuối deque không còn cần thiết.
- Để tìm Maximum trong cửa sổ: Duy trì deque giảm dần (từ trước ra sau). Khi thêm phần tử mới, pop các phần tử nhỏ hơn ở cuối deque. Phần tử lớn nhất luôn nằm ở đầu deque.
- Để tìm Minimum trong cửa sổ: Duy trì deque tăng dần (từ trước ra sau). Khi thêm phần tử mới, pop các phần tử lớn hơn ở cuối deque. Phần tử nhỏ nhất luôn nằm ở đầu deque.
Ứng dụng cơ bản 1: Maximum trong cửa sổ trượt (Sliding Window Maximum)
Bài toán: Cho một mảng các số nums và một kích thước cửa sổ k, tìm giá trị lớn nhất trong mỗi cửa sổ con có kích thước k khi cửa sổ trượt từ trái sang phải.
Ví dụ: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Các cửa sổ và giá trị lớn nhất:
[1, 3, -1]: max = 3[3, -1, -3]: max = 3[-1, -3, 5]: max = 5[-3, 5, 3]: max = 5[5, 3, 6]: max = 6[3, 6, 7]: max = 7 Kết quả mong muốn:[3, 3, 5, 5, 6, 7]
Giải pháp với Monotonic Queue:
Chúng ta sẽ sử dụng std::deque<int> để lưu trữ chỉ số của các phần tử trong cửa sổ hiện tại, duy trì chúng theo thứ tự giảm dần về giá trị.
Khi duyệt qua mảng từ trái sang phải với chỉ số i:
- Loại bỏ các chỉ số cũ: Nếu chỉ số ở đầu deque (
dq.front()) nằm ngoài cửa sổ hiện tại (tức làdq.front() == i - k), thì pop nó ra khỏi đầu deque. - Duy trì tính đơn điệu: Trong khi deque không rỗng VÀ phần tử tại chỉ số ở cuối deque (
nums[dq.back()]) nhỏ hơn hoặc bằng phần tử hiện tại (nums[i]), pop chỉ số đó ra khỏi cuối deque. Điều này đảm bảo rằng các phần tử nhỏ hơn ở cuối deque không bao giờ là maximum và sẽ không cản trở việc tìm max ở đầu. - Thêm chỉ số hiện tại: Push chỉ số
ivào cuối deque (dq.push_back(i)). - Ghi nhận kết quả: Nếu
iđã đạt đến vị trí mà cửa sổ có kích thướckđầu tiên được hình thành (tức lài >= k - 1), thì phần tử lớn nhất trong cửa sổ hiện tại chính là phần tử tại chỉ số ở đầu deque (nums[dq.front()]). Ghi nhận giá trị này vào mảng kết quả.
#include <iostream>
#include <vector>
#include <deque>
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int n = nums.size();
std::vector<int> result; // Lưu kết quả
std::deque<int> dq; // Deque lưu trữ chỉ số, duy trì giảm dần theo giá trị nums[index]
// Duyệt mảng từ trái sang phải
for (int i = 0; i < n; ++i) {
// 1. Loại bỏ chỉ số ở đầu deque nếu nó nằm ngoài cửa sổ hiện tại
// Cửa sổ hiện tại kết thúc ở i, bắt đầu ở i - k + 1.
// Nếu chỉ số đầu deque <= i - k, nghĩa là nó ở bên trái ngoài cửa sổ.
if (!dq.empty() && dq.front() <= i - k) {
dq.pop_front();
}
// 2. Duy trì tính đơn điệu giảm dần:
// Loại bỏ các chỉ số ở cuối deque mà phần tử tương ứng nhỏ hơn hoặc bằng phần tử hiện tại nums[i]
// Vì nums[i] lớn hơn hoặc bằng các phần tử này, và nó nằm ở vị trí sau (chỉ số i > dq.back()),
// nên nums[i] sẽ là ứng cử viên tốt hơn cho maximum trong các cửa sổ sau này.
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
// 3. Thêm chỉ số hiện tại vào cuối deque
dq.push_back(i);
// 4. Ghi nhận kết quả khi cửa sổ đủ kích thước k
// Cửa sổ đầu tiên đủ kích thước khi i = k - 1
if (i >= k - 1) {
// Phần tử lớn nhất trong cửa sổ hiện tại luôn nằm ở đầu deque
result.push_back(nums[dq.front()]);
}
}
// In kết quả
std::cout << "Original Array: ";
for (int x : nums) {
std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "Sliding Window Maximum (k=" << k << "): ";
for (int res : result) {
std::cout << res << " ";
}
std::cout << std::endl;
return 0;
}
Giải thích code:
- Chúng ta sử dụng
std::deque<int> dq;để lưu trữ các chỉ số. Deque cho phép thêm/xóa hiệu quả ở cả hai đầu (push_back,pop_front,pop_back,front). - Vòng lặp
for (int i = 0; i < n; ++i)duyệt qua mảng.ilà chỉ số kết thúc của cửa sổ hiện tại. if (!dq.empty() && dq.front() <= i - k): Dòng này xử lý việc loại bỏ các chỉ số cũ ra khỏi cửa sổ. Nếu chỉ số ở đầu deque (dq.front()) nhỏ hơn hoặc bằng chỉ số bắt đầu của cửa sổ hiện tại (i - k), nó không còn nằm trong cửa sổ, nên pop nó ra.while (!dq.empty() && nums[dq.back()] <= nums[i]): Đây là bước duy trì tính đơn điệu giảm dần. Nếu phần tử hiện tại (nums[i]) lớn hơn hoặc bằng phần tử tại chỉ số ở cuối deque (nums[dq.back()]), thìnums[dq.back()]không bao giờ có thể là maximum trong các cửa sổ sau này mànums[i]còn hiện diện (vìnums[i]lớn hơn hoặc bằng nó và nằm ở vị trí sau). Do đó, chúng ta loại bỏ (pop_back()) các chỉ số như vậy.dq.push_back(i);: Chỉ số hiện tạiiluôn được thêm vào cuối deque.if (i >= k - 1): Khiiđạt đếnk-1, cửa sổ đầu tiên có kích thướck(nums[0]đếnnums[k-1]) được hình thành. Từ đây trở đi, ở mỗi bước, đầu deque (dq.front()) luôn chứa chỉ số của phần tử lớn nhất trong cửa sổ hiện tại.result.push_back(nums[dq.front()]);: Thêm giá trị lớn nhất của cửa sổ hiện tại vào mảng kết quả.
Độ phức tạp:
- Thời gian: O(N). Mỗi chỉ số được push vào deque tối đa một lần và pop ra khỏi deque tối đa hai lần (một lần từ cuối để duy trì đơn điệu, một lần từ đầu khi ra khỏi cửa sổ). Các thao tác deque là O(1).
- Không gian: O(k) trong trường hợp xấu nhất (ví dụ: cửa sổ hiện tại chứa dãy giảm dần), khi tất cả
kchỉ số trong cửa sổ đều nằm trong deque.
Biến thể: Minimum trong cửa sổ trượt
Để tìm giá trị nhỏ nhất trong cửa sổ trượt, chúng ta chỉ cần thay đổi điều kiện duy trì tính đơn điệu. Thay vì duy trì deque giảm dần, chúng ta duy trì deque tăng dần.
Khi thêm phần tử mới nums[i], chúng ta loại bỏ các chỉ số ở cuối deque mà phần tử tương ứng lớn hơn hoặc bằng nums[i]. Phần tử nhỏ nhất trong cửa sổ sẽ luôn nằm ở đầu deque.
Bài tập ví dụ:
Ngăn xếp và Hàng đợi
Trong một buổi đàm phán kinh doanh quốc tế, FullHouse Dev đã nhận được một thử thách thú vị từ đối tác Nissan. Họ cần phải tối ưu hóa quy trình xử lý các đơn hàng bằng cách sử dụng cả ngăn xếp và hàng đợi.
Bài toán
FullHouse Dev được cung cấp một ngăn xếp gồm \(N\) số nguyên, trong đó phần tử đầu tiên đại diện cho đỉnh của ngăn xếp và phần tử cuối cùng đại diện cho đáy của ngăn xếp. Họ cần lấy ra ít nhất một phần tử từ ngăn xếp. Tại một thời điểm bất kỳ, họ có thể chuyển đổi ngăn xếp thành hàng đợi, trong đó đáy của ngăn xếp sẽ trở thành đầu của hàng đợi. Sau khi chuyển đổi, không thể chuyển hàng đợi trở lại thành ngăn xếp. Nhiệm vụ là loại bỏ đúng \(K\) phần tử sao cho tổng của \(K\) phần tử được loại bỏ là lớn nhất.
INPUT FORMAT:
- Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách.
- Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách biểu diễn các phần tử của ngăn xếp.
OUTPUT FORMAT:
- In ra tổng lớn nhất có thể của \(K\) phần tử đã loại bỏ.
Ràng buộc:
- Giới hạn thời gian: 1 giây
- Giới hạn bộ nhớ: 256MB
Ví dụ
INPUT
10 5
10 9 1 2 3 4 5 6 7 8OUTPUT
40Giải thích
- Lấy ra hai phần tử từ ngăn xếp: {10, 9}
- Sau đó chuyển ngăn xếp thành hàng đợi và lấy ra ba phần tử đầu tiên từ hàng đợi: {8, 7, 6}
- Tổng lớn nhất có thể là: 10 + 9 + 8 + 7 + 6 = 40 Đây là hướng giải bài Ngăn xếp và Hàng đợi:
Phân tích bài toán:
- Ta có một mảng ban đầu biểu diễn ngăn xếp, với phần tử đầu là đỉnh.
- Có thể lấy
pphần tử từ đỉnh (tức làpphần tử đầu tiên của mảng ban đầu). Điều kiện làp >= 1(lấy ít nhất một phần tử từ ngăn xếp). - Sau khi lấy
pphần tử, chuyển phần còn lại sang hàng đợi. Đáy ngăn xếp cũ (phần tử cuối cùng của mảng ban đầu) trở thành đầu hàng đợi. - Từ hàng đợi, lấy thêm
qphần tử từ đầu (tức làqphần tử cuối cùng của mảng ban đầu, theo thứ tự ngược lại của ngăn xếp cũ). - Tổng số phần tử lấy ra là
p + q = K. - Mục tiêu: Tối đa hóa tổng
Kphần tử được chọn.
Xác định cấu trúc các phần tử được chọn: Nếu lấy
pphần tử từ đỉnh ngăn xếp ban đầu vàqphần tử từ hàng đợi sau khi chuyển đổi:pphần tử lấy từ đỉnh ngăn xếp chính làpphần tử đầu tiên của mảng ban đầu.qphần tử lấy từ đầu hàng đợi chính làqphần tử cuối cùng của mảng ban đầu (vì đáy ngăn xếp cũ là đầu hàng đợi mới).- Vậy, ta sẽ chọn
pphần tử đầu tiên vàqphần tử cuối cùng của mảng ban đầu, sao chop + q = Kvàp >= 1.
Xác định phạm vi của
p:plà số phần tử lấy từ đỉnh ngăn xếp. Theo yêu cầu "lấy ra ít nhất một phần tử từ ngăn xếp", ta cóp >= 1.- Tổng số phần tử lấy ra là
K, nênp <= K. - Số phần tử lấy từ cuối mảng là
q = K - p. Ta cần lấyqphần tử từ cuối mảng, điều này khả thi nếu mảng đủ dài (N >= K). - Vậy,
pcó thể chạy từ1đếnK.
Thuật toán:
- Đọc N, K và mảng N số nguyên
A. - Khởi tạo biến
max_sumvới giá trị rất nhỏ. - Duyệt qua tất cả các khả năng chọn
pphần tử từ đỉnh ngăn xếp, vớipchạy từ1đếnK.- Với mỗi giá trị
p, số phần tử lấy từ hàng đợi sẽ làq = K - p. - Tính tổng của
pphần tử đầu tiên của mảngA(các phần tử từA[0]đếnA[p-1]). - Tính tổng của
qphần tử cuối cùng của mảngA(các phần tử từA[N-q]đếnA[N-1]). - Tổng hiện tại là tổng của hai phần này.
- Cập nhật
max_sumnếu tổng hiện tại lớn hơn.
- Với mỗi giá trị
- In ra
max_sum.
- Đọc N, K và mảng N số nguyên
Tối ưu hóa tính tổng:
- Việc tính tổng
pphần tử đầu vàqphần tử cuối trong mỗi bước lặp sẽ mất thời gian O(p + q) = O(K). LặpKlần sẽ tốn O(K^2), quá chậm với N, K lên tới 100000. - Sử dụng Mảng Tổng Tiền Tố (Prefix Sum) và Mảng Tổng Hậu Tố (Suffix Sum).
- Tính mảng
prefix_sum:prefix_sum[i]là tổng các phần tử từA[0]đếnA[i-1].prefix_sum[0] = 0,prefix_sum[i] = prefix_sum[i-1] + A[i-1]vớii=1..N. Tổngpphần tử đầu tiên làprefix_sum[p]. - Tính mảng
suffix_sum:suffix_sum[i]là tổng các phần tử từA[i]đếnA[N-1].suffix_sum[N] = 0,suffix_sum[i] = suffix_sum[i+1] + A[i]vớii=N-1..0. Tổngqphần tử cuối cùng (từA[N-q]đếnA[N-1]) chính làsuffix_sum[N-q].
- Tính mảng
- Với Prefix Sum và Suffix Sum, tổng của
pphần tử đầu vàq = K-pphần tử cuối được tính trong O(1) làprefix_sum[p] + suffix_sum[N - (K - p)].
- Việc tính tổng
Thuật toán tối ưu:
- Đọc N, K và mảng
A. - Xây dựng mảng
prefix_sumkích thướcN+1. - Xây dựng mảng
suffix_sumkích thướcN+1. - Khởi tạo
max_sumvới giá trị rất nhỏ (ví dụ: tổngKphần tử nhỏ nhất có thể). - Lặp
ptừ1đếnK:- Số phần tử từ cuối:
q = K - p. - Tính tổng:
current_sum = prefix_sum[p] + suffix_sum[N - q]. max_sum = max(max_sum, current_sum).
- Số phần tử từ cuối:
- In
max_sum.
- Đọc N, K và mảng
Làm thêm nhiều bài tập miễn phí tại đây
Khóa học liên quan
Giảm giá!
Comments