Tuyên bố vấn đề
Cho một mảng gồm n phần tử dương, chúng ta cần tìm tổng thấp nhất có thể của các phần tử max và min trong một mảng con với điều kiện kích thước của mảng con phải lớn hơn 2.
Ví dụ
Nếu arr [] ={10, 5, 15, 7, 2, 1, 3} thì tổng “max + min” là 3 khi chúng ta thêm “2 + 1”.
Thuật toán
- Việc thêm bất kỳ phần tử nào vào một mảng con sẽ không làm tăng tổng của tối đa và tối thiểu.
- Vì giá trị tối đa của một mảng sẽ không bao giờ giảm khi thêm các phần tử vào mảng. Nó sẽ chỉ tăng lên nếu chúng ta thêm các phần tử lớn hơn. Vì vậy, luôn luôn là tối ưu nếu chỉ xem xét những mảng con có độ dài 2.
- Do đó, hãy xem xét tất cả các mảng con có độ dài 2 và so sánh tổng và lấy giá trị nhỏ nhất.
Ví dụ
#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 bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Đầu ra
Maximum sum = 3