ผลรวมแฝดสูงสุดในอาร์เรย์ใน C ++

ในปัญหานี้ เราจะได้รับอาร์เรย์ งานของเราคือสร้างโปรแกรมที่จะหาผลรวมแฝดสูงสุดในอาร์เรย์ นั่นคือ ค้นหาชุดขององค์ประกอบสามตัวที่ผลรวมสูงสุด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − อาร์เรย์ ={4, 6, 1, 2}

ผลผลิต − 12

คำอธิบาย −

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

วิธีง่ายๆ วิธีหนึ่งในการแก้ปัญหาคือสิ่งที่เราได้อธิบายไว้ในตัวอย่าง ซึ่งก็คือการนำค่าผลรวมสำหรับคู่แฝดสามทั้งหมดแล้วหาค่าสูงสุดของคู่นั้น แต่วิธีนี้ไม่ได้ผลเนื่องจากความยาวของแฝดสามจะมาก

ในวิธีนี้ เราจะเรียกใช้สามลูปที่จะค้นหาผลรวมแฝดที่เป็นไปได้ทั้งหมด และหากผลรวมของแฝดสามนี้มากกว่าค่า maxsum เราจะเริ่มต้นผลรวมแฝดนี้เป็นค่าสูงสุด

ตัวอย่าง

โปรแกรมเพื่อแสดงโซลูชันของเรา

#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;
}

ผลลัพธ์

The maximum triplet sum of the array is 21

วิธีที่มีประสิทธิภาพคือการเรียงลำดับอาร์เรย์แล้วค้นหาผลรวมขององค์ประกอบสามตัวสุดท้ายของอาร์เรย์ซึ่งจะเป็นผลรวมสูงสุดของแฝดสาม

ตัวอย่าง

โปรแกรมเพื่อแสดงวิธีแก้ปัญหา

#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;
}

ผลลัพธ์

The maximum triplet sum of the array is 24