数据结构
网络
关系型数据库管理系统
操作系统
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+ 浏览量
广告