Đề bài
Cho hai mảng đã sắp xếp, có thể có phần tử chung. Tìm tổng đường đi lớn nhất từ đầu một mảng đến cuối một trong hai mảng. Chỉ được chuyển từ mảng này sang mảng kia tại các phần tử chung. Các phần tử chung không nhất thiết cùng chỉ số.
Độ phức tạp mong đợi O(m+n), m, n là số phần tử của arr1, arr2.
Ví dụ
Input: arr1[] = {2, 3, 7, 10, 12} arr2[] = {1, 5, 7, 8} Output: 35 (1 + 5 + 7 + 10 + 12) = 35- Bắt đầu từ phần tử đầu arr2 là 1, đi đến 5, rồi 7.
- Tại 7 (phần tử chung), chuyển sang arr1, duyệt 10 và 12.
Thuật toán
- Ý tưởng tương tự quy trình merge của merge sort. Tính tổng các phần tử giữa các điểm chung cho cả hai mảng. Khi gặp điểm chung, so sánh hai tổng, lấy lớn hơn cộng vào kết quả.
- Khởi tạo result = 0, sum1 = 0, sum2 = 0 (tổng giữa hai điểm chung).
- Duyệt cả hai mảng. So sánh phần tử hiện tại
- nếu arr1[i] < arr2[j], cộng vào sum1, i++
- nếu arr1[i] > arr2[j], cộng vào sum2, j++
- nếu bằng nhau, result += max(sum1, sum2), reset sum1, sum2 = 0, cộng phần tử chung vào result, tăng cả i, j
- Sau vòng lặp, cộng phần tử còn lại vào sum1, sum2, result += max(sum1, sum2)
Ví dụ
#include <bits/stdc++.h> using namespace std; int max(int x, int y){ return (x > y)? x : y; } int maxPathSum(int *arr1, int *arr2, int m, int n){ int i = 0, j = 0; int result = 0, sum1 = 0, sum2 = 0; while (i < m && j < n) { if (arr1[i] < arr2[j]) { sum1 += arr1[i++]; } else if (arr1[i] > arr2[j]) { sum2 += arr2[j++]; } else { result += max(sum1, sum2); sum1 = 0, sum2 = 0; while (i < m && j < n && arr1[i] == arr2[j]) { result = result + arr1[i++]; j++; } } } while (i < m) { sum1 += arr1[i++]; } while (j < n) { sum2 += arr2[j++]; } result += max(sum1, sum2); return result; } int main(){ int arr1[] = {2, 3, 7, 10, 12}; int arr2[] = {1, 5, 7, 8}; int m = sizeof(arr1)/sizeof(arr1[0]); int n = sizeof(arr2)/sizeof(arr2[0]); cout << "Tổng đường đi lớn nhất = " << maxPathSum(arr1, arr2, m, n) << endl; return 0; }Kết quả
Tổng đường đi lớn nhất = 35