Tổng bộ ba lớn nhất trong mảng trong C++

Trong bài toán này, chúng ta được cho một mảng. Nhiệm vụ là tạo một chương trình tìm tổng bộ ba lớn nhất trong mảng, tức là tìm tập hợp ba phần tử có tổng lớn nhất.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào – mảng = {4, 6, 1, 2}

Đầu ra – 12

Giải thích –

tất cả các bộ ba:
(4, 6, 1) = 4+6+1 = 11
(4, 6, 2) = 4+6+2 = 12
(4, 1, 2) = 4+1+2 = 7
(6, 1, 2) = 6+1+2 = 9
Tổng bộ ba lớn nhất là 12

Một cách tiếp cận đơn giản để giải quyết bài toán là như chúng ta đã mô tả trong ví dụ: lấy giá trị tổng cho tất cả các cặp bộ ba và sau đó tìm giá trị lớn nhất của chúng. Nhưng cách này không hiệu quả vì với độ dài mảng lớn, số lượng bộ ba sẽ trở nên lớn.

Trong phương pháp này, chúng ta sẽ chạy ba vòng lặp tìm tất cả các tổng bộ ba có thể và nếu tổng bộ ba này lớn hơn maxsum thì chúng ta sẽ gán tổng bộ ba này làm maxsum.

Ví dụ

Chương trình minh họa giải pháp của chúng ta:

#include <iostream>
using namespace std;
int maxSum(int arr[], int n){
    int maxSum = 0;
    int i, j, k;
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++)
            for (k = j + 1; k < n; k++)
                if (maxSum < arr[i] + arr[j] + arr[k]) maxSum = arr[i] + arr[j] + arr[k];
    return maxSum;
}
int main(){
    int arr[] = { 3, 5, 7 ,1, 9, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Tổng bộ ba lớn nhất của mảng là "<<maxSum(arr, n);
    return 0;
}

Kết quả

Tổng bộ ba lớn nhất của mảng là 21

Một cách tiếp cận hiệu quả sẽ là sắp xếp mảng và sau đó tìm tổng của ba phần tử cuối cùng của mảng, đó sẽ là tổng lớn nhất của các bộ ba.

Ví dụ

Chương trình minh họa giải pháp:

#include <bits/stdc++.h>
using namespace std;
int maxSum(int arr[], int n) {
    sort(arr, arr + n);
    return arr[n - 1] + arr[n - 2] + arr[n - 3];
}
int main() {
    int arr[] = { 3, 5, 9, 1, 2, 8, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Tổng bộ ba lớn nhất của mảng là "<<maxSum(arr, n);
    return 0;
}

Kết quả

Tổng bộ ba lớn nhất của mảng là 24