Giải thích chi tiết code tìm tích vô hướng lớn nhất giữa hai dãy con cùng độ dài
Tôi sẽ giải thích từng phần của code đã được cải tiến để tìm giá trị tích vô hướng lớn nhất giữa hai dãy con cùng độ dài từ hai mảng A và B.
Cấu trúc chính của chương trình
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// Đọc input
int n;
cin >> n;
vector<int> A(n), B(n);
for (int i = 0; i < n; i++) cin >> A[i];
for (int i = 0; i < n; i++) cin >> B[i];
// Biến lưu kết quả
long long max_product = LLONG_MIN;
// Thuật toán chính
for (int delta = -n + 1; delta <= n - 1; delta++) {
// Xác định vùng giao nhau giữa hai mảng với độ dời delta
int start_A = max(0, -delta);
int start_B = max(0, delta);
int len = min(n - start_A, n - start_B);
// Thuật toán Kadane để tìm tổng con lớn nhất
long long current_sum = 0;
long long max_window = LLONG_MIN;
for (int i = 0; i < len; i++) {
current_sum += (long long)A[start_A + i] * B[start_B + i];
if (current_sum > max_window) {
max_window = current_sum;
}
if (current_sum < 0) {
current_sum = 0;
}
}
// Cập nhật giá trị lớn nhất tổng thể
if (max_window > max_product) {
max_product = max_window;
}
}
// In kết quả
cout << max_product << endl;
return 0;
}
Giải thích từng phần
1. Phần khởi tạo và đọc input
cpp
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Tối ưu tốc độ đọc input bằng cách tắt đồng bộ hóa với thư viện C
cpp
int n;
cin >> n;
vector<int> A(n), B(n);
for (int i = 0; i < n; i++) cin >> A[i];
for (int i = 0; i < n; i++) cin >> B[i];
Đọc số phần tử n
Khởi tạo 2 vector A và B với kích thước n
Đọc lần lượt các phần tử của mảng A và B
2. Biến lưu kết quả
cpp
long long max_product = LLONG_MIN;
Khởi tạo giá trị lớn nhất ban đầu bằng giá trị nhỏ nhất của kiểu long long
3. Thuật toán chính
cpp
for (int delta = -n + 1; delta <= n - 1; delta++)
Duyệt tất cả các độ lệch (delta) có thể giữa hai mảng
delta có giá trị từ -n+1 đến n-1, đại diện cho tất cả cách dịch chuyển tương đối giữa hai mảng
cpp
int start_A = max(0, -delta);
int start_B = max(0, delta);
int len = min(n - start_A, n - start_B);
Tính toán vị trí bắt đầu trong mảng A và B cho độ lệch hiện tại
len là độ dài tối đa của dãy con có thể so sánh với độ lệch này
4. Thuật toán Kadane tìm tổng con lớn nhất
cpp
long long current_sum = 0;
long long max_window = LLONG_MIN;
for (int i = 0; i < len; i++) {
current_sum += (long long)A[start_A + i] * B[start_B + i];
if (current_sum > max_window) {
max_window = current_sum;
}
if (current_sum < 0) {
current_sum = 0;
}
}
current_sum: tổng tích vô hướng hiện tại
max_window: giá trị lớn nhất của cửa sổ hiện tại
Với mỗi phần tử trong dãy con:
Cộng dồn tích của cặp phần tử tương ứng vào current_sum
Cập nhật max_window nếu current_sum lớn hơn
Nếu current_sum âm, reset về 0 (vì tổng âm sẽ không giúp tăng tổng các phần tử tiếp theo)
5. Cập nhật giá trị lớn nhất tổng thể
cpp
if (max_window > max_product) {
max_product = max_window;
}
So sánh giá trị lớn nhất của cửa sổ hiện tại với giá trị lớn nhất tổng thể
Cập nhật nếu tìm thấy giá trị lớn hơn
6. In kết quả
cpp
cout << max_product << endl;
In ra giá trị tích vô hướng lớn nhất tìm được
Tại sao thuật toán này hiệu quả?
Độ phức tạp O(n^2):
Vòng lặp ngoài chạy 2n-1 lần (các giá trị delta)
Vòng lặp trong (Kadane) chạy tối đa n lần
Tổng cộng độ phức tạp là O(n^2)
Tối ưu bộ nhớ:
Chỉ sử dụng một số biến đếm và biến tạm
Không cần lưu trữ mảng phụ trung gian lớn
Tận dụng thuật toán Kadane:
Hiệu quả để tìm dãy con có tổng lớn nhất
Xử lý được cả trường hợp có phần tử âm
Với cách tiếp cận này, chương trình sẽ tìm được chính xác giá trị tích vô hướng lớn nhất giữa hai dãy con cùng độ dài từ hai mảng A và B, kể cả với input lớn (n=5000).
teudepdzai
Created at
0 likes