資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢陣列中三個數的最大和，使得 i < j < k 且 a[i] < a[j] < a[k]
概念
對於給定大小為 n 的正整數陣列，我們的任務是確定三元組 (ai + aj + ak) 的最大和，使得 0 <= i < j < k < n 且 ai< aj< ak。
輸入
a[] = 3 6 4 2 5 10
輸出
19
解釋
All possible triplets are:- 3 4 5 => sum = 12 3 6 10 => sum = 19 3 4 10 => sum = 17 4 5 10 => sum = 19 2 5 10 => sum = 17 Maximum sum = 19
方法
現在，一種**簡單的方法**是使用三個巢狀的“for 迴圈”遍歷每個三元組，並逐個確定並更新所有三元組的和。這裡，這種方法的時間複雜度為 O(n^3)，對於較大的“n”值來說是不夠的。
此外，我們可以應用一種**更好的方法**來進一步最佳化上述方法。在這種方法中，我們可以使用兩個巢狀迴圈，而不是使用三個巢狀迴圈遍歷每個三元組。
在遍歷每個數字（例如中間元素 (aj)）時，確定其前面小於 aj 的最大數字 (ai) 和其後面大於 aj 的最大數字 (ak)。最後，現在使用計算出的 ai + aj + ak 的和更新最大答案。
示例
// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;
// Shows function to calculate maximum triplet sum
int maxTripletSum(int arr1[], int n1){
// Used to initialize the answer
int ans1 = 0;
for (int i = 1; i < n1 - 1; ++i) {
int max1 = 0, max2 = 0;
// Determine maximum value(less than arr1[i])
// from i+1 to n1-1
for (int j = 0; j < i; ++j)
if (arr1[j] < arr1[i])
max1 = max(max1, arr1[j]);
// Determine maximum value(greater than arr1[i])
// from i+1 to n1-1
for (int j = i + 1; j < n1; ++j)
if (arr1[j] > arr1[i])
max2 = max(max2, arr1[j]);
// store maximum answer
if(max1 && max2)
ans1=max(ans1,max1+arr1[i]+max2);
}
return ans1;
}
// Driver code
int main(){
int Arr[] = { 3, 6, 4, 2, 5, 10 };
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << maxTripletSum(Arr, N);
return 0;
}輸出
19
更新於: 2020-07-25
1K+ 瀏覽量
廣告