Đề bài
Cho mảng n phần tử dương, cần tìm tổng nhỏ nhất có thể của phần tử lớn nhất và nhỏ nhất trong một mảng con, với điều kiện kích thước mảng con lớn hơn hoặc bằng 2.
Ví dụ
Nếu arr[] = {10, 5, 15, 7, 2, 1, 3} thì tổng "max + min" là 3 khi cộng "2 + 1".
Thuật toán
- Thêm bất kỳ phần tử nào vào mảng con sẽ không làm tăng tổng của max và min.
- Vì max của mảng không bao giờ giảm khi thêm phần tử. Chỉ tăng nếu thêm phần tử lớn hơn. Vì vậy luôn tối ưu khi chỉ xét các mảng con có độ dài 2.
- Do đó xét tất cả mảng con độ dài 2, so sánh tổng và lấy tối thiểu.
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; int getMaxSum(int *arr, int n) { if (n < 2) { return -1; } int result = arr[0] + arr[1]; for (int i = 1; i + 1 < n; ++i) { result = min(result, (arr[i] + arr[i + 1])); } return result; } int main() { int arr[] = {10, 5, 15, 7, 2, 1, 3}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Maximum sum = " << getMaxSum(arr, n) << endl; return 0; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Maximum sum = 3