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

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

本文概述

给定一个长度为n的正整数数组。求出当0 <= i < j < k < n且ai < aj < ak时的三元组(ai + aj + ak)的最大和。

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}

首先, 在继续解决方案之前。

简单方法是通过三个嵌套的" for循环"遍历每个三元组, 并逐一更新所有三元组的总和。该方法的时间复杂度为O(n3), 这对于" n"的较大值是不够的。

更好的方法是要在上述方法中做进一步的优化。与遍历具有三个嵌套循环的每个三元组不同, 我们可以遍历两个嵌套循环。遍历每个数字时(假定为中间元素(aĴ)), 找出最大数量(a一世)小于Ĵ在它之前和最大数量(aķ)大于aĴ超越它。现在, 在此之后, 用计算出的总和更新最大答案一世+一个Ĵ+一个ķ 

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)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: