Tổng bộ ba tối đa trong mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng. Nhiệm vụ của chúng ta là tạo một chương trình sẽ 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à lớn nhất.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra - 12

Giải thích -

all triplets are :
(4, 6, 1) = 4+6+1 = 11
(4, 6, 2) = 4+6+1 = 12
(4, 1, 2) = 4+6+1 = 7
(6, 1, 2) = 4+6+1 = 9
The maximum triplet sum is 12

Một cách tiếp cận đơn giản để giải quyết vấn đề là những gì chúng ta đã mô tả trong ví dụ, đó là lấy tổng các giá trị 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 làm này không hiệu quả vì với độ dài của tất cả các cặp sinh ba sẽ trở nên lớn.

Trong phương pháp này, chúng tôi sẽ chạy ba vòng lặp để tìm tất cả các bộ ba tổng có thể có và nếu tổng của bộ ba này lớn hơn giá trị tối đa thì chúng tôi sẽ khởi tạo tổng bộ ba này dưới dạng tối đa.

Ví dụ

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

#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<<"The maximum triplet sum of the array is "<<maxSum(arr, n);
   return 0;
}

Đầu ra

The maximum triplet sum of the array is 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<<"The maximum triplet sum of the array is "<<maxSum(arr, n);
   return 0;
}

Đầu ra

The maximum triplet sum of the array is 24