NỘI DUNG
Giới thiệu về bài toán
Bài toán này được gọi là “tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp” hoặc “maximum subarray problem”. Về cơ bản, bài toán này yêu cầu tìm một mảng con liên tiếp trong một mảng cho trước sao cho tổng của các phần tử trong mảng con đó là lớn nhất.
Ví dụ, với mảng số nguyên [−2, 1, −3, 4, −1, 2, 1, −5, 4], ta có thể tìm được mảng con liên tiếp có tổng lớn nhất là [4, −1, 2, 1], có tổng bằng 6.
Các thuật toán
Có nhiều phương pháp để giải quyết bài toán này, bao gồm:
-
Brute force: đây là phương pháp đơn giản nhất, trong đó ta duyệt qua tất cả các mảng con có thể trong mảng cho trước và tính tổng của từng mảng con. Độ phức tạp của phương pháp này là O(n^3), n là kích thước của mảng.
-
Dynamic programming: phương pháp này dựa trên việc tính toán các tổng con liên tiếp và sử dụng kết quả tính được để tìm tổng lớn nhất. Độ phức tạp của phương pháp này là O(n).
-
Divide and conquer: phương pháp này chia mảng ban đầu thành hai nửa, tìm mảng con lớn nhất trong từng nửa và sau đó tìm mảng con lớn nhất chứa phần tử ở giữa. Độ phức tạp của phương pháp này là O(nlogn).
-
Kadane’s algorithm: đây là phương pháp tối ưu nhất, sử dụng một biến để lưu trữ tổng của các phần tử trong mảng con liên tiếp và cập nhật biến này khi ta duyệt qua mảng. Độ phức tạp của phương pháp này là O(n).
Tùy vào tình huống cụ thể và giới hạn thời gian, ta có thể lựa chọn phương pháp phù hợp để giải quyết bài toán này.
Cài đặt các thuật toán
Cài đặt Brute force với Python
Để cài đặt phương pháp Brute force cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp bằng Python, ta có thể sử dụng hai vòng lặp để duyệt qua tất cả các mảng con có thể trong mảng cho trước và tính tổng của từng mảng con. Sau đó, ta chọn mảng con có tổng lớn nhất làm kết quả.
Dưới đây là mã nguồn Python cho phương pháp Brute force:
def max_subarray_brute_force(arr):
max_sum = arr[0]
n = len(arr)
for i in range(n):
for j in range(i+1, n+1):
sub_arr = arr[i:j]
sub_sum = sum(sub_arr)
if sub_sum > max_sum:
max_sum = sub_sum
max_subarray = sub_arr
return max_subarray, max_sum
Cài đặt Brute force với C++
Để cài đặt phương pháp Brute force cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp bằng C++, ta cũng có thể sử dụng hai vòng lặp để duyệt qua tất cả các mảng con có thể trong mảng cho trước và tính tổng của từng mảng con. Sau đó, ta chọn mảng con có tổng lớn nhất làm kết quả.
Dưới đây là mã nguồn C++ cho phương pháp Brute force:
#include <iostream>
#include <vector>
using namespace std;
vector<int> max_subarray_brute_force(vector<int>& arr) {
int max_sum = arr[0];
vector<int> max_subarray;
int n = arr.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
int sub_sum = 0;
vector<int> sub_arr;
for (int k = i; k < j; k++) {
sub_sum += arr[k];
sub_arr.push_back(arr[k]);
}
if (sub_sum > max_sum) {
max_sum = sub_sum;
max_subarray = sub_arr;
}
}
}
return max_subarray;
}
Cài đặt Dynamic programmin với Python
Để cài đặt phương pháp Dynamic Programming cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp bằng Python, ta có thể sử dụng phương pháp quy hoạch động để tính toán và lưu trữ các giá trị trung gian, nhằm giảm thiểu độ phức tạp của bài toán.
Dưới đây là mã nguồn Python cho phương pháp Dynamic Programming:
def max_subarray_dp(arr):
n = len(arr)
dp = [0] * n # Khởi tạo mảng dp với giá trị 0
dp[0] = arr[0] # Gán giá trị cho dp[0]
for i in range(1, n):
dp[i] = max(dp[i-1] + arr[i], arr[i]) # Tính giá trị mới cho dp[i]
max_sum = max(dp) # Tìm giá trị lớn nhất trong mảng dp
start = dp.index(max_sum) # Tìm vị trí bắt đầu của mảng con lớn nhất
end = start
sub_sum = max_sum
for i in range(start-1, -1, -1):
sub_sum -= arr[i]
if sub_sum == 0:
end = i
break
max_subarray = arr[end:start+1] # Lấy mảng con lớn nhất
return max_subarray
Cài đặt Dynamic programmin với C++
Để cài đặt phương pháp Dynamic Programming cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp bằng C++, ta có thể sử dụng phương pháp quy hoạch động để tính toán và lưu trữ các giá trị trung gian, nhằm giảm thiểu độ phức tạp của bài toán.
Dưới đây là mã nguồn C++ cho phương pháp Dynamic Programming:
#include <bits/stdc++.h>
using namespace std;
vector<int> max_subarray_dp(vector<int>& arr) {
int n = arr.size();
vector<int> dp(n);
dp[0] = arr[0];
int max_sum = dp[0], start = 0, end = 0, sub_sum = 0;
for (int i = 1; i < n; i++) {
dp[i] = max(dp[i-1] + arr[i], arr[i]);
if (dp[i] > max_sum) {
max_sum = dp[i];
end = i;
}
}
sub_sum = max_sum;
for (int i = end; i >= 0; i--) {
sub_sum -= arr[i];
if (sub_sum == 0) {
start = i;
break;
}
}
vector<int> max_subarray(arr.begin() + start, arr.begin() + end + 1);
return max_subarray;
}
int main() {
vector<int> arr = {2, -1, 3, 5, -2, 4};
vector<int> max_subarray = max_subarray_dp(arr);
for (int i = 0; i < max_subarray.size(); i++) {
cout << max_subarray[i] << " ";
}
return 0;
}
Cài đặt Divide and conquer với Python
Để cài đặt phương pháp Divide and Conquer cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp bằng Python, ta có thể sử dụng đệ quy để chia nhỏ bài toán thành các bài toán con nhỏ hơn, sau đó kết hợp kết quả từ các bài toán con đó để tìm ra kết quả cuối cùng. Dưới đây là mã nguồn Python cho phương pháp Divide and Conquer:
def max_subarray_divide_conquer(arr, low, high):
if low == high:
return [arr[low]]
mid = (low + high) // 2
left_subarray = max_subarray_divide_conquer(arr, low, mid)
right_subarray = max_subarray_divide_conquer(arr, mid+1, high)
max_left_sum = max_left_border_sum = float('-inf')
left_sum = 0
for i in range(mid, low-1, -1):
left_sum += arr[i]
if left_sum > max_left_sum:
max_left_sum = left_sum
max_right_sum = max_right_border_sum = float('-inf')
right_sum = 0
for i in range(mid+1, high+1):
right_sum += arr[i]
if right_sum > max_right_sum:
max_right_sum = right_sum
max_border_sum = max_left_border_sum + max_right_border_sum
return max(left_subarray, right_subarray, max_border_sum)
Cài đặt Divide and conquer với C++
Để cài đặt phương pháp Divide and Conquer cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp bằng C++, ta có thể sử dụng đệ quy để chia nhỏ bài toán thành các bài toán con nhỏ hơn, sau đó kết hợp kết quả từ các bài toán con đó để tìm ra kết quả cuối cùng. Dưới đây là mã nguồn C++ cho phương pháp Divide and Conquer:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<int> max_subarray_cross(vector<int>& arr, int low, int mid, int high) {
int max_left_sum = INT_MIN;
int left_sum = 0;
int max_left_index = mid;
for (int i = mid; i >= low; i--) {
left_sum += arr[i];
if (left_sum > max_left_sum) {
max_left_sum = left_sum;
max_left_index = i;
}
}
int max_right_sum = INT_MIN;
int right_sum = 0;
int max_right_index = mid + 1;
for (int i = mid + 1; i <= high; i++) {
right_sum += arr[i];
if (right_sum > max_right_sum) {
max_right_sum = right_sum;
max_right_index = i;
}
}
vector<int> result;
result.push_back(max_left_index);
result.push_back(max_right_index);
result.push_back(max_left_sum + max_right_sum);
return result;
}
vector<int> max_subarray_divide_conquer(vector<int>& arr, int low, int high) {
if (low == high) {
return vector<int>{low, high, arr[low]};
}
int mid = (low + high) / 2;
vector<int> left_result = max_subarray_divide_conquer(arr, low, mid);
vector<int> right_result = max_subarray_divide_conquer(arr, mid + 1, high);
vector<int> cross_result = max_subarray_cross(arr, low, mid, high);
if (left_result[2] >= right_result[2] && left_result[2] >= cross_result[2]) {
return left_result;
}
else if (right_result[2] >= left_result[2] && right_result[2] >= cross_result[2]) {
return right_result;
}
else {
return cross_result;
}
}
int main() {
vector<int> arr = { -2, -5, 6, -2, -3, 1, 5, -6 };
vector<int> result = max_subarray_divide_conquer(arr, 0, arr.size() - 1);
cout << "Maximum subarray sum: " << result[2] << endl;
cout << "Starting index: " << result[0] << endl;
cout << "Ending index: " << result[1] << endl;
return 0;
}
Cài đặt Kadane’s algorithm với Python
Để cài đặt thuật toán Kadane’s trong Python cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp, ta có thể sử dụng một vòng lặp để duyệt qua từng phần tử của mảng và tính toán tổng của mảng con liên tiếp hiện tại (tức là tính toán sum_curr), sau đó so sánh nó với giá trị lớn nhất hiện tại (tức là max_so_far), và nếu sum_curr lớn hơn max_so_far thì gán max_so_far bằng sum_curr. Nếu sum_curr trở về giá trị âm, ta gán sum_curr bằng 0 vì một mảng con liên tiếp có tổng âm sẽ không bao giờ làm tăng tổng của mảng con liên tiếp lớn hơn.
Dưới đây là mã nguồn Python cho thuật toán Kadane’s:
def max_subarray_kadane(arr):
max_so_far = arr[0]
sum_curr = 0
start_index = 0
end_index = 0
temp_start_index = 0
for i in range(len(arr)):
sum_curr += arr[i]
if sum_curr > max_so_far:
max_so_far = sum_curr
start_index = temp_start_index
end_index = i
if sum_curr < 0:
sum_curr = 0
temp_start_index = i + 1
return start_index, end_index, max_so_far
Cài đặt Kadane’s algorithm với C++
Để cài đặt thuật toán Kadane’s trong C++ cho bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp, ta cũng sử dụng một vòng lặp để duyệt qua từng phần tử của mảng và tính toán tổng của mảng con liên tiếp hiện tại (tức là tính toán sum_curr), sau đó so sánh nó với giá trị lớn nhất hiện tại (tức là max_so_far), và nếu sum_curr lớn hơn max_so_far thì gán max_so_far bằng sum_curr. Nếu sum_curr trở về giá trị âm, ta gán sum_curr bằng 0 vì một mảng con liên tiếp có tổng âm sẽ không bao giờ làm tăng tổng của mảng con liên tiếp lớn hơn.
Dưới đây là mã nguồn C++ cho thuật toán Kadane’s:
#include <iostream>
#include <vector>
using namespace std;
vector<int> max_subarray_kadane(vector<int> arr) {
int max_so_far = arr[0];
int sum_curr = 0;
int start_index = 0;
int end_index = 0;
int temp_start_index = 0;
for (int i = 0; i < arr.size(); i++) {
sum_curr += arr[i];
if (sum_curr > max_so_far) {
max_so_far = sum_curr;
start_index = temp_start_index;
end_index = i;
}
if (sum_curr < 0) {
sum_curr = 0;
temp_start_index = i + 1;
}
}
vector<int> result = {start_index, end_index, max_so_far};
return result;
}
int main() {
vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
vector<int> result = max_subarray_kadane(arr);
cout << "Start index: " << result[0] << endl;
cout << "End index: " << result[1] << endl;
cout << "Max subarray sum: " << result[2] << endl;
return 0;
}
Kết luận và đánh giá độ phức tạp của các thuật toán
Trong toàn bộ nội dung đã cài đặt, chúng ta đã làm việc với các thuật toán như Brute Force, Dynamic Programming, Divide and Conquer và Kadane’s algorithm để giải quyết bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp.
Độ phức tạp thời gian và không gian của các thuật toán này khác nhau, tùy thuộc vào cách triển khai cụ thể và kích thước đầu vào của bài toán. Tuy nhiên, ở đây chúng ta có thể xem xét độ phức tạp trung bình của từng thuật toán:
- Brute Force:
- Độ phức tạp thời gian: O(n^3)
- Độ phức tạp không gian: O(1)
- Dynamic Programming:
- Độ phức tạp thời gian: O(n)
- Độ phức tạp không gian: O(n)
- Divide and Conquer:
- Độ phức tạp thời gian: O(n log n)
- Độ phức tạp không gian: O(log n)
- Kadane’s algorithm:
- Độ phức tạp thời gian: O(n)
- Độ phức tạp không gian: O(1)
Với các bài toán nhỏ, Brute Force là một lựa chọn tốt. Tuy nhiên, nếu kích thước đầu vào lớn, độ phức tạp của Brute Force là rất cao và không khả thi trong thực tế.
Dynamic Programming và Divide and Conquer cung cấp các giải pháp tối ưu cho bài toán này, tuy nhiên chúng cần sử dụng một lượng lớn bộ nhớ hơn so với Kadane’s algorithm, đặc biệt là trong trường hợp các bài toán có kích thước lớn.
Kadane’s algorithm là thuật toán đơn giản và hiệu quả nhất trong số các thuật toán này, với độ phức tạp thời gian và không gian tối ưu hơn. Vì vậy, nếu chỉ cần tìm kiếm tổng lớn nhất của các phần tử trong mảng con liên tiếp, Kadane’s algorithm là một lựa chọn tốt nhất.
Trong bài viết này, chúng ta đã đề cập đến 4 thuật toán khác nhau để giải quyết bài toán tìm tổng lớn nhất của các phần tử trong mảng con liên tiếp, đó là Brute Force, Dynamic Programming, Divide and Conquer và Kadane’s algorithm.
Mỗi thuật toán đều có ưu và nhược điểm riêng, và có thể phù hợp với những trường hợp sử dụng khác nhau. Ví dụ, trong trường hợp kích thước đầu vào nhỏ, Brute Force có thể là lựa chọn tốt nhất, trong khi Kadane’s algorithm lại phù hợp với các bài toán kích thước lớn hơn. Dynamic Programming và Divide and Conquer cũng đều cung cấp các giải pháp tối ưu, nhưng có độ phức tạp không gian và thời gian lớn hơn Kadane’s algorithm.
Thông qua bài viết này, chúng ta hi vọng rằng bạn đã có được một cái nhìn tổng quan về 4 thuật toán này và có thể áp dụng chúng vào giải quyết các bài toán tương tự./.