# 求数组中i < j < k和a[i] < a[j] < a[k]的三元组最大和

2021年3月16日15:26:09 发表评论 354 次浏览

## 本文概述

``````Input: a[] = 2 5 3 1 4 9
Output: 16

Explanation:
All possible triplets are:-
2 3 4 => sum = 9
2 5 9 => sum = 16
2 3 9 => sum = 14
3 4 9 => sum = 16
1 4 9 => sum = 14
Maximum sum = 16``````

{IDE}

## C ++

``````// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;

// Function to calculate maximum triplet sum
int maxTripletSum( int arr[], int n)
{
// Initialize the answer
int ans = 0;

for ( int i = 1; i < n - 1; ++i) {
int max1 = 0, max2 = 0;

// find maximum value(less than arr[i])
// from 0 to i-1
for ( int j = 0; j < i; ++j)
if (arr[j] < arr[i])
max1 = max(max1, arr[j]);

// find maximum value(greater than arr[i])
// from i+1 to n-1
for ( int j = i + 1; j < n; ++j)
if (arr[j] > arr[i])
max2 = max(max2, arr[j]);

// store maximum answer
if (max1 && max2)
ans=max(ans, max1+arr[i]+max2);
}

return ans;
}

// Driver code
int main()
{
int arr[] = { 2, 5, 3, 1, 4, 9 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << maxTripletSum(arr, n);
return 0;
}``````

## Java

``````// Java program to find maximum triplet sum

import java.io.*;
import java.math.*;

class GFG {

// Function to calculate maximum triplet sum
static int maxTripletSum( int arr[], int n)
{
// Initialize the answer
int ans = 0 ;

for ( int i = 1 ; i < n - 1 ; ++i) {
int max1 = 0 , max2 = 0 ;

// find maximum value(less than arr[i])
// from 0 to i-1
for ( int j = 0 ; j < i; ++j)
if (arr[j] < arr[i])
max1 = Math.max(max1, arr[j]);

// find maximum value(greater than arr[i])
// from i+1 to n-1
for ( int j = i + 1 ; j < n; ++j)
if (arr[j] > arr[i])
max2 = Math.max(max2, arr[j]);

// store maximum answer
if (max1 && max2)
ans = Math.max(ans, max1 + arr[i] + max2);
}

return ans;
}

// Driver code
public static void main(String args[])
{
int arr[] = { 2 , 5 , 3 , 1 , 4 , 9 };
int n = arr.length;
System.out.println(maxTripletSum(arr, n));
}
}

// This code is contributed by Nikita Tiwari.``````

## Python3

``````# Python 3 program to
# find maximum triplet sum

# Function to calculate
# maximum triplet sum
def maxTripletSum(arr, n) :

# Initialize the answer
ans = 0

for i in range ( 1 , (n - 1 )) :
max1 = 0
max2 = 0

# find maximum value(less than arr[i])
# from 0 to i-1
for j in range ( 0 , i) :
if (arr[j] < arr[i]) :
max1 = max (max1, arr[j])

# find maximum value(greater than arr[i])
# from i + 1 to n-1
for j in range ((i + 1 ), n) :
if (arr[j] > arr[i]) :
max2 = max (max2, arr[j])

# store maximum answer
if (max1 && max2):
ans = max (ans, max1 + arr[i] + max2)

return ans

# Driver code

arr = [ 2 , 5 , 3 , 1 , 4 , 9 ]
n = len (arr)
print (maxTripletSum(arr, n))

# This code is contributed
# by Nikita Tiwari.``````

## C#

``````// C# program to find maximum triplet sum
using System;

class GFG {

// Function to calculate maximum triplet sum
static int maxTripletSum( int [] arr, int n)
{

// Initialize the answer
int ans = 0;

for ( int i = 1; i < n - 1; ++i)
{
int max1 = 0, max2 = 0;

// find maximum value(less than
// arr[i]) from 0 to i-1
for ( int j = 0; j < i; ++j)
if (arr[j] < arr[i])
max1 = Math.Max(max1, arr[j]);

// find maximum value(greater than
// arr[i]) from i+1 to n-1
for ( int j = i + 1; j < n; ++j)
if (arr[j] > arr[i])
max2 = Math.Max(max2, arr[j]);

// store maximum answer
if (max1 && max2)
ans = Math.Max(ans, max1 + arr[i] + max2);
}

return ans;
}

// Driver code
public static void Main()
{

int [] arr = { 2, 5, 3, 1, 4, 9 };
int n = arr.Length;

Console.WriteLine(maxTripletSum(arr, n));
}
}

// This code is contributed by vt_m.``````

## 的PHP

``````<?php
// PHP program to find maximum triplet sum

// Function to calculate maximum triplet sum
function maxTripletSum( \$arr , \$n )
{

// Initialize the answer
\$ans = 0;

for ( \$i = 1; \$i < \$n - 1; ++ \$i )
{
\$max1 = 0; \$max2 = 0;

// find maximum value(less than
// arr[i]) from 0 to i-1
for ( \$j = 0; \$j < \$i ; ++ \$j )
if ( \$arr [ \$j ] < \$arr [ \$i ])
\$max1 = max( \$max1 , \$arr [ \$j ]);

// find maximum value(greater than
// arr[i]) from i+1 to n-1
for ( \$j = \$i + 1; \$j < \$n ; ++ \$j )
if ( \$arr [ \$j ] > \$arr [ \$i ])
\$max2 = max( \$max2 , \$arr [ \$j ]);

// store maximum answer
if ( \$max1 && \$max2 )
\$ans = max( \$ans , \$max1 + \$arr [ \$i ] + \$max2 );
}

return \$ans ;
}

// Driver code
\$arr = array (2, 5, 3, 1, 4, 9);
\$n = sizeof( \$arr );
echo maxTripletSum( \$arr , \$n );

// This code is contributed by nitin mittal.
?>``````

``16``

2

)

O(1)

• 为了找到最大数大于大于给定数的最大数, 我们可以维护最大后缀数组数组, 使得对于任何数字(后缀一世), 它将包含索引i, i + 1, …n-1中的最大值。后缀数组可以用O(n)时间计算。
• 为了找到小于其前面给定数字的最大数字, 我们可以在给定数字之前维护一个排序的数字列表, 这样我们就可以简单地执行二进制搜索以找到一个刚好小于给定数字的数字。在C ++语言中, 我们可以使用组STL库的关联容器。

## C ++

``````// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;

// Utility function to get the lower last min
// value of 'n'
int getLowValue(set< int >& lowValue, int & n)
{
auto it = lowValue.lower_bound(n);

// Since 'lower_bound' returns the first
// iterator greater than 'n', thus we
// have to decrement the pointer for
// getting the minimum value
--it;

return (*it);
}

// Function to calculate maximum triplet sum
int maxTripletSum( int arr[], int n)
{
// Initialize suffix-array
int maxSuffArr[n + 1];

// Set the last element
maxSuffArr[n] = 0;

// Calculate suffix-array containing maximum
// value for index i, i+1, i+2, ... n-1 in
// arr[i]
for ( int i = n - 1; i >= 0; --i)
maxSuffArr[i] = max(maxSuffArr[i + 1], arr[i]);

int ans = 0;

// Initialize set container
set< int > lowValue;

// Insert minimum value for first comparison
// in the set
lowValue.insert(INT_MIN);

for ( int i = 0; i < n - 1; ++i) {
if (maxSuffArr[i + 1] > arr[i]) {
ans = max(ans, getLowValue(lowValue, arr[i])
+ arr[i] + maxSuffArr[i + 1]);

// Insert arr[i] in set<> for further
// processing
lowValue.insert(arr[i]);
}
}
return ans;
}

// Driver code
int main()
{
int arr[] = { 2, 5, 3, 1, 4, 9 };
int n = sizeof (arr) / sizeof (arr[0]);

cout << maxTripletSum(arr, n);
return 0;
}``````

``16``

O(n * log(n))

O(n)