Trong bài toán này, chúng ta được cung cấp một mảng arr []. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng lớn nhất của nhỏ nhất và nhỏ nhất thứ hai trong một mảng.
Mô tả sự cố - Ta cần tìm tổng các phần tử nhỏ nhất và nhỏ nhất thứ hai của một mảng con tổng của mảng. Và trả về giá trị tối đa của tất cả các tổng của mảng con như vậy.
Ví dụ
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {3, 5, 4, 2, 9, 1, 6} Đầu ra
11
Giải thích
Their out of all subarrays possible,
{2, 9} has a maximum sum of smallest elements.
Sum = 2 + 9 = 11 Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tạo ra tất cả các mảng con. Tìm phần tử nhỏ nhất và nhỏ nhất thứ hai, tìm tổng. Trả lại tất cả sumof tối đa.
Một giải pháp khác hiệu quả hơn là dựa trên việc quan sát các ví dụ. Muốn tìm tổng lớn nhất sẽ là tổng của hai cặp tỷ lệ liên tiếp của mảng. Và chúng ta sẽ tìm ra cặp tổng lớn nhất.
Thuật toán
Khởi tạo -
maxSum = −1
Bước 1 -
loop i −> 0 to n−1
Bước 1.1 -
if maxSum < (arr[i] + arr[i+1]). Then, maxSum = (arr[i] + arr[i+1])
Bước 2 -
Return maxSum.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <iostream>
using namespace std;
int calcMaxSumPairs(int arr[], int n) {
int maxSum = −1;
for (int i=0; i< (n − 1); i++)
if(maxSum < (arr[i] + arr[i + 1]))
maxSum = (arr[i] + arr[i + 1]);
return maxSum;
}
int main() {
int arr[] = {3, 4, 2, 9, 5, 6};
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum sum of smallest and second smallest in an
array is "<<calcMaxSumPairs(arr, n);
return 0;
} Đầu ra
The maximum sum of smallest and second smallest in an array is 14