Given an array, the task is to find the maximum triplet sum in the array.
Example 1:
Input : arr[ ] = {4, 2, 7, 9}
Output : 20
Explanation:
Here are total 4 combination: 
(0, 1, 2),(0, 1, 3),(0, 2, 3),(1, 2, 3).
So, the Sum of these combinations is 
13,15, 20,and 18.The maximum sum is 20.
 
Example 2:
Input : arr[ ] = {1, 0, 8, 6, 4, 2} 
Output : 18 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maxTripletSum() that takes an array (arr), sizeOfArray (n), and return the maximum triplet sum in the array. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
3 ≤ N ≤ 10^{5}
-10^{5} ≤ A[i] ≤ 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3



class Solution:

    def maxTripletSum (self, arr,  n) : 

        #Complete the function



Solutions:
class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		arr = arr[::-1]
		return sum(arr[:3])


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort(reverse=True)
		return arr[0] + arr[1] + arr[2]


class Solution:

	def maxTripletSum(self, a, n):
		a.sort()
		return a[-1] + a[-2] + a[-3]


class Solution:

	def maxTripletSum(self, a, n):
		a.sort()
		b = a[::-1]
		sum = 0
		for i in range(3):
			sum += int(b[i])
		return sum


class Solution:

	def maxTripletSum(self, arr, n):
		first_max = max(arr)
		arr.remove(max(arr))
		second_max = max(arr)
		arr.remove(max(arr))
		third_max = max(arr)
		return first_max + second_max + third_max


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		sum = 0
		for i in range(n - 3, n):
			sum += arr[i]
		return sum


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		return arr[-1] + arr[-2] + arr[-3]


class Solution:

	def maxTripletSum(self, A, n):
		A.sort()
		return A[n - 1] + A[n - 2] + A[n - 3]


class Solution:

	def maxTripletSum(self, arr, n):
		a = b = c = -100000000.0
		for i in arr:
			if i > a:
				c = b
				b = a
				a = i
			elif i >= b:
				c = b
				b = i
			elif i >= c:
				c = i
		return a + b + c


class Solution:

	def maxTripletSum(self, arr, n):
		first = -(1 * 10 ** 5 + 1)
		second = -(1 * 10 ** 5 + 2)
		third = -(1 * 10 ** 5 + 3)
		for item in arr:
			if item > first:
				third = second
				second = first
				first = item
				continue
			if item > second:
				third = second
				second = item
				continue
			if item > third:
				third = item
				continue
		return first + second + third


class Solution:

	def maxTripletSum(self, arr, n):
		arr = sorted(arr, reverse=True)
		s = sum(arr[0:3])
		return s


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		if len(arr) >= 3:
			x = arr[n - 1] + arr[n - 2] + arr[n - 3]
			return x
		else:
			return -1


import math

class Solution:

	def maxTripletSum(self, arr, n):
		mx = -math.inf
		smx = -math.inf
		tmx = -math.inf
		for num in arr:
			if num >= mx:
				tmx = smx
				smx = mx
				mx = num
			elif num >= smx:
				tmx = smx
				smx = num
			elif num >= tmx:
				tmx = num
		return mx + smx + tmx


class Solution:

	def maxTripletSum(self, arr, n):
		m1 = max(arr)
		arr.remove(m1)
		m2 = max(arr)
		arr.remove(m2)
		m3 = max(arr)
		return m1 + m2 + m3


class Solution:

	def maxTripletSum(self, arr, n):
		a = sorted(arr)
		return a[-1] + a[-2] + a[-3]


class Solution:

	def maxTripletSum(self, arr, n):
		f = -1000000
		s = -1000000
		t = -1000000
		for i in range(n):
			if arr[i] >= f:
				t = s
				s = f
				f = arr[i]
			elif arr[i] >= s:
				t = s
				s = arr[i]
			elif arr[i] >= t:
				t = arr[i]
		return f + s + t


class Solution:

	def maxTripletSum(self, arr, n):
		l1 = -99999
		l2 = -99999
		l3 = -99999
		for i in range(n):
			if arr[i] > l3:
				(l3, arr[i]) = (arr[i], l3)
			if l3 > l2:
				(l3, l2) = (l2, l3)
			if l2 > l1:
				(l1, l2) = (l2, l1)
		return l1 + l2 + l3


class Solution:

	def maxTripletSum(self, arr, n):
		a = max(arr)
		arr.remove(a)
		b = max(arr)
		arr.remove(b)
		c = max(arr)
		arr.remove(c)
		return a + b + c


class Solution:

	def maxTripletSum(self, arr, n):
		s = 0
		arr.sort(reverse=True)
		for i in range(3):
			s += arr[i]
		return s


class Solution:

	def maxTripletSum(self, arr: list, n: int) -> int:
		x = self.findMaxIndex(arr)
		y = self.findMaxIndex(arr, x)
		z = self.findMaxIndex(arr, x, y)
		return arr[x] + arr[y] + arr[z]

	@staticmethod
	def findMaxIndex(lst: list, first_max=None, second_max=None) -> int:
		(max_index, max_value) = (None, float('-inf'))
		for (index, value) in enumerate(lst):
			if index == first_max or index == second_max:
				continue
			elif value > max_value:
				(max_index, max_value) = (index, value)
		return max_index


class Solution:

	def maxTripletSum(self, arr, n):
		a = sorted(arr)
		b = a.pop(n - 1)
		c = a.pop(n - 2)
		d = a.pop(n - 3)
		return b + c + d


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		b = arr[-3:]
		return sum(b)


class Solution:

	def maxTripletSum(self, arr, n):
		max1 = -1000000
		max2 = -1000000
		max3 = -1000000
		for i in arr:
			if i > max1:
				max3 = max2
				max2 = max1
				max1 = i
			elif i > max2:
				max3 = max2
				max2 = i
			elif i > max3:
				max3 = i
		return max1 + max2 + max3


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		m = arr[-1]
		m1 = arr[-2]
		m2 = arr[-3]
		return m + m1 + m2


class Solution:

	def maxTripletSum(self, arr, n):
		arr = sorted(arr)
		sumi = 0
		sumi = arr[n - 1] + arr[n - 2] + arr[n - 3]
		return sumi


class Solution:

	def maxTripletSum(self, arr, n):
		first = float('-inf')
		second = float('-inf')
		third = float('-inf')
		for i in arr:
			if i > first:
				third = second
				second = first
				first = i
			elif i > second:
				third = second
				second = i
			elif i > third:
				third = i
		return first + second + third


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		j = n - 1
		i = j - 2
		return arr[i] + arr[i + 1] + arr[j]


class Solution:

	def maxTripletSum(self, arr, n):
		maxA = -10000000
		maxB = -10000000
		maxC = -10000000
		for i in range(n):
			if arr[i] > maxA:
				maxC = maxB
				maxB = maxA
				maxA = arr[i]
			elif arr[i] > maxB:
				maxC = maxB
				maxB = arr[i]
			elif arr[i] > maxC:
				maxC = arr[i]
		return maxA + maxB + maxC


class Solution:

	def maxTripletSum(self, a, n):
		fir = float('-inf') + 2
		sec = float('-inf') + 1
		tir = float('-inf')
		for i in a:
			if i >= fir:
				(fir, sec, tir) = (i, fir, sec)
			elif i >= sec:
				(sec, tir) = (i, sec)
			elif i > tir:
				tir = i
		return fir + sec + tir


class Solution:

	def maxTripletSum(self, arr, n):
		m1 = -float('inf')
		m2 = -float('inf')
		m3 = -float('inf')
		for i in range(n):
			if arr[i] > m1:
				m3 = m2
				m2 = m1
				m1 = arr[i]
			elif arr[i] > m2:
				m3 = m2
				m2 = arr[i]
			elif arr[i] > m3:
				m3 = arr[i]
		return m1 + m2 + m3


class Solution:

	def maxTripletSum(self, arr, n):
		summ1 = 0
		arr = sorted(arr, reverse=True)
		for i in range(3):
			summ1 += arr[i]
		return summ1


class Solution:

	def maxTripletSum(self, arr, n):
		maxA = -999999
		maxB = -999999
		maxC = -999999
		for i in range(0, n):
			if arr[i] > maxA:
				temp = maxC
				maxC = maxB
				maxB = maxA
				maxA = arr[i]
			elif arr[i] > maxB:
				temp = maxC
				maxC = maxB
				maxB = arr[i]
			elif arr[i] > maxC:
				maxC = arr[i]
		return maxA + maxB + maxC


class Solution:

	def maxTripletSum(self, arr, n):
		s = 0
		arr.sort()
		l = 3
		while l > 0:
			s += arr[n - l]
			l -= 1
		return s


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		sum1 = 0
		sum1 = sum(arr[n - 3:n])
		return sum1


class Solution:

	def maxTripletSum(self, arr, n):
		if n == 3:
			return sum(arr)
		first = arr[0]
		second = float('-inf')
		third = float('-inf')
		for i in range(1, n):
			if arr[i] > first:
				third = second
				second = first
				first = arr[i]
				continue
			elif arr[i] > second:
				third = second
				second = arr[i]
				continue
			elif arr[i] > third:
				third = arr[i]
		return first + second + third


class Solution:

	def maxTripletSum(self, arr, n):
		res = 0
		arr.sort(reverse=True)
		return sum(arr[:3])


class Solution:

	def maxTripletSum(self, arr, n):
		arr = sorted(arr)[::-1]
		return sum(arr[:3])


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort(reverse=True)
		return sum(arr[0:3])
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n)
	print(res)


class Solution:

	def maxTripletSum(self, arr, n):
		first = -10000
		sec = -10000
		th = -10000
		for i in range(0, n):
			if arr[i] > first:
				th = sec
				sec = first
				first = arr[i]
			elif arr[i] > sec:
				th = sec
				sec = arr[i]
			elif arr[i] > th:
				th = arr[i]
		return first + sec + th
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n)
	print(res)


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		return arr[-1] + arr[-2] + arr[-3]
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n)
	print(res)


class Solution:

	def maxTripletSum(self, arr, n):
		max1 = -123456
		max2 = -123456
		max3 = -123456
		for i in range(n):
			if arr[i] > max1:
				max3 = max2
				max2 = max1
				max1 = arr[i]
			elif arr[i] > max2:
				max3 = max2
				max2 = arr[i]
			elif arr[i] > max3:
				max3 = arr[i]
		return max1 + max2 + max3
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n)
	print(res)


class Solution:

	def maxTripletSum(self, arr, n):
		arr = sorted(arr)
		summ = 0
		for i in range(n - 1, n - 1 - 3, -1):
			summ += arr[i]
		return summ
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	res = ob.maxTripletSum(arr, n)
	print(res)


class Solution:

	def maxTripletSum(self, a, n):
		t = max(a)
		a.remove(t)
		t += max(a)
		a.remove(max(a))
		return t + max(a)


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort(reverse=True)
		if n >= 3:
			return arr[0] + arr[1] + arr[2]
		else:
			return 0


class Solution:

	def maxTripletSum(self, arr, n):
		mx1 = -9999999
		mx2 = -9999999
		mx3 = -9999999
		for i in range(n):
			if arr[i] > mx1:
				mx3 = mx2
				mx2 = mx1
				mx1 = arr[i]
			elif arr[i] > mx2:
				mx3 = mx2
				mx2 = arr[i]
			elif arr[i] > mx3:
				mx3 = arr[i]
		return mx1 + mx2 + mx3


class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		summ = 0
		if n > 2:
			summ = arr[n - 1] + arr[n - 2] + arr[n - 3]
		return summ


from itertools import combinations

class Solution:

	def maxTripletSum(self, arr, n):
		arr.sort()
		return arr[n - 1] + arr[n - 2] + arr[n - 3]


class Solution:

	def maxTripletSum(self, arr, n):
		x = float('-inf')
		y = float('-inf')
		z = float('-inf')
		for i in arr:
			if i > z:
				x = y
				y = z
				z = i
			elif i > y:
				x = y
				y = i
			elif i > x:
				x = i
		return x + y + z