Tìm tổng lớn nhất của các bộ ba trong một mảng sao cho i <j <k và a [i] <a [j] <a [k] trong C ++

Khái niệm

Đối với một mảng các số nguyên dương có kích thước n đã cho, nhiệm vụ của chúng ta là xác định tổng số tối đa của bộ ba (a _i + a _j + a _k ) sao cho 0 <=i i j k .

Đầu vào

 a [] =3 6 4 2 5 10

Đầu ra

Giải thích

 Tất cả các bộ ba có thể có là:-3 4 5 => sum =123 6 10 => sum =193 4 10 => sum =174 5 10 => sum =192 5 10 => sum =17 Tổng tối đa =19   Phương pháp 
 
 Bây giờ, một  cách tiếp cận đơn giản  là truy cập cho mỗi bộ ba với ba "vòng lặp for" lồng nhau và xác định cập nhật tổng của tất cả các bộ ba lần lượt. Ở đây, độ phức tạp về thời gian của phương pháp này là O (n ^ 3), không đủ cho giá trị cao hơn của ‘n’. 
 
 Một lần nữa, chúng tôi có thể áp dụng  cách tiếp cận tốt hơn  để thực hiện tối ưu hóa hơn nữa trong cách tiếp cận trên. Trong phương pháp này, thay vì truy cập qua mọi bộ ba với ba vòng lặp lồng nhau, chúng ta có thể truy cập qua hai vòng lặp lồng nhau. 
 
 Tại thời điểm truy cập qua từng số (giả sử như phần tử ở giữa (a _j )), xác định số lượng tối đa (a _i ) ít hơn một _j đứng trước nó và số tối đa (ak) lớn hơn một _j ngoài nó. Cuối cùng, bây giờ, hãy cập nhật câu trả lời tối đa với tổng được tính toán của một _i + a _j + a _k 
  Ví dụ 
  // Chương trình C ++ để tìm tổng bộ ba lớn nhất # include  using namespace std; // Hiển thị hàm để tính toán bộ ba tối đa sumint maxTripletSum (int arr1 [], int n1) {// Dùng để khởi tạo câu trả lời int ans1 =0; for (int i =1; i  arr1 [i ]) max2 =max (max2, arr1 [j]); // lưu trữ câu trả lời tối đa if (max1 &&max2) ans1 =max (ans1, max1 + arr1 [i] + max2); } return ans1;} // Trình điều khiển codeint main () {int Arr [] ={3, 6, 4, 2, 5, 10}; int N =sizeof (Arr) / sizeof (Arr [0]); cout <  Đầu ra 
  19