Find Maximum Sum of Triplets in an Array in Python

Suppose we have an array of positive numbers, there are n elements in that array, we have to find the maximum sum of triplet (ai + aj + ak ) such that 0 <= i < j < k < n and ai< aj< ak.

So, if the input is like A = [3,6,4,2,5,10], then the output will be 19 as 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. So the max is 19

To solve this, we will follow these steps −

• n := size of A

• res := 0

• for i in range 1 to n - 1, do

  • first_max := 0, second_max := 0

  • for j in range 0 to i, do

    • if A[j] < A[i], then

      • first_max := maximum of first_max, A[j]

  • for j in range i + 1 to n, do

    • if A[j] > A[i], then

      • second_max := maximum of second_max, A[j]

  • if first_max and second_max is non-zero, then

    • res := maximum of res, first_max + A[i] + second_max

• return res

Example

Let us see the following implementation to get better understanding −

 Live Demo

def get_max_triplet_sum(A) :
   n = len(A)
   res = 0
   for i in range(1, (n - 1)) :
      first_max = 0
      second_max = 0
      for j in range(0, i) :
         if (A[j] < A[i]) :
            first_max = max(first_max, A[j])
      for j in range((i + 1), n) :
         if (A[j] > A[i]) :
            second_max = max(second_max, A[j])
      if (first_max and second_max):
         res = max(res, first_max + A[i] + second_max)
   return res
A = [3,6,4,2,5,10]
print(get_max_triplet_sum(A))

Input

[3,6,4,2,5,10]

Output

19