Given an Array of non-negative integers. Find out the maximum perimeter of the triangle from the array.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {6, 1, 6, 5, 8, 4}
Output : 20
Explanation:
Triangle formed by  8,6 & 6. Thus 
perimeter 20.
Ã¢â¬â¹Example 2:
Input : arr[ ] = {7, 55, 20, 1, 4, 33, 12} 
Output :  -1
Explanation:
As the triangle is not possible because 
the condition: the sum of two sides should 
be greater than third is not fulfilled here.
 
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 maxPerimeter() that takes an array (arr), sizeOfArray (n), and return an integer displaying the maximum perimeter of the triangle is possible else print -1. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(1).
Constraints:
3 ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: #User function Template for python3





def maxPerimeter (arr, n) : 

    #Complete the function





Solutions:
def maxPerimeter(arr, n):
	arr.sort()
	for i in reversed(range(n - 2)):
		if arr[i] + arr[i + 1] > arr[i + 2]:
			return arr[i] + arr[i + 1] + arr[i + 2]
	return -1


def maxPerimeter(arr, n):
	if n < 3:
		return -1
	arr.sort(reverse=True)
	maxs = -1
	for i in range(2, n):
		if arr[i] + arr[i - 1] > arr[i - 2]:
			return arr[i] + arr[i - 1] + arr[i - 2]
	return -1


def maxPerimeter(arr, n):
	if n < 3:
		return -1
	arr.sort(reverse=True)
	mx = -1
	for index in range(n - 2):
		two_sides = arr[index + 1] + arr[index + 2]
		if arr[index] < two_sides:
			mx = two_sides + arr[index] if two_sides + arr[index] > mx else mx
	return mx


def maxPerimeter(arr, n):
	arr.sort()
	j = n - 1
	while j > 1:
		if arr[j] + arr[j - 1] > arr[j - 2] and arr[j - 1] + arr[j - 2] > arr[j] and (arr[j] + arr[j - 2] > arr[j - 1]):
			return arr[j] + arr[j - 1] + arr[j - 2]
			break
		else:
			j -= 1
	return -1


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	maxi = -1
	for i in range(0, n - 2):
		if arr[i] < arr[i + 1] + arr[i + 2]:
			maxi = max(maxi, arr[i] + arr[i + 1] + arr[i + 2])
	return maxi


def maxPerimeter(arr, n):
	arr = sorted(arr)[::-1]
	for i in range(1, n - 1):
		if arr[i] + arr[i + 1] > arr[i - 1]:
			return arr[i - 1] + arr[i] + arr[i + 1]
	return -1


def maxPerimeter(arr, n):
	arr.sort()
	arr.reverse()
	a = [0, 0, 1]
	for i in range(n - 3):
		a = arr[i:i + 3]
		a.sort()
		if min(a) + a[1] < a[2]:
			pass
		else:
			return sum(a)
			break
	return -1


def maxPerimeter(arr, n):
	p = 0
	arr.sort(reverse=False)
	for i in range(n - 1, 0, -1):
		if i - 1 >= 0 and i - 2 >= 0:
			a = arr[i]
			b = arr[i - 1]
			c = arr[i - 2]
			if a < b + c:
				p = max(p, a + b + c)
	if p == 0:
		return -1
	else:
		return p


def maxPerimeter(arr, n):
	arr.sort()
	max = -1
	for i in range(n - 1, 2, -1):
		if arr[i] < arr[i - 1] + arr[i - 2]:
			max = arr[i] + arr[i - 1] + arr[i - 2]
			break
	return max


def maxPerimeter(arr, n):
	arr.sort()
	m = -1
	for j in range(n - 2):
		a = arr[j]
		b = arr[j + 1]
		c = arr[j + 2]
		if a + b > c and b + c > a and (a + c > b):
			if a + b + c > m:
				m = a + b + c
	return m


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	ans = -1
	for i in range(2, n):
		if arr[i - 2] < arr[i] + arr[i - 1]:
			ans = arr[i] + arr[i - 1] + arr[i - 2]
			break
	return ans


def maxPerimeter(a, n):
	max = -1
	a.sort()
	for i in range(n - 1, 1, -1):
		if max < a[i] + a[i - 1] + a[i - 2] and a[i] < a[i - 1] + a[i - 2]:
			max = a[i] + a[i - 1] + a[i - 2]
	return max


def maxPerimeter(arr, n):
	maxi = 0
	n = len(arr)
	arr.sort(reverse=True)
	for i in range(0, n - 2):
		if arr[i] < arr[i + 1] + arr[i + 2]:
			maxi = max(maxi, arr[i] + arr[i + 1] + arr[i + 2])
			break
	if maxi == 0:
		return -1
	else:
		return str(maxi)


def maxPerimeter(arr, n):
	arr.sort()
	mx = -9
	for i in range(n - 2):
		if arr[i] + arr[i + 1] > arr[i + 2]:
			mx = max(mx, arr[i] + arr[i + 1] + arr[i + 2])
	if mx > -9:
		return mx
	else:
		return -1


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	i = 0
	while i <= n - 3:
		a = arr[i]
		b = arr[i + 1]
		c = arr[i + 2]
		if b + c > a:
			return a + b + c
		else:
			i += 1
	return -1


def maxPerimeter(arr, n):
	a = []
	arr.sort()
	for i in range(n - 2):
		if arr[i] + arr[i + 1] > arr[i + 2]:
			sum1 = sum(arr[i:i + 3])
			a.append(sum1)
	return -1 if len(a) == 0 else max(a)


def maxPerimeter(arr, n):
	arr.sort()
	i = n - 1
	i1 = n - 2
	i3 = n - 3
	while i3 >= 0:
		if arr[i1] + arr[i3] > arr[i] and arr[i] + arr[i1] > arr[i3] and (arr[i3] + arr[i] > arr[i1]):
			return arr[i1] + arr[i3] + arr[i]
		i1 = i1 - 1
		i3 = i3 - 1
		i = i - 1
	return -1


def maxPerimeter(arr, n):
	a = []
	arr.sort(reverse=True)
	for i in range(0, n - 2):
		if arr[i] < arr[i + 1] + arr[i + 2]:
			a.append(arr[i] + arr[i + 1] + arr[i + 2])
	if a:
		return max(a)
	else:
		return -1


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	a1 = []
	if n < 3:
		return -1
	elif n == 3 and arr[0] < arr[1] + arr[2]:
		return sum(arr)
	else:
		for i in range(len(arr) - 2):
			if arr[i] < arr[i + 1] + arr[i + 2]:
				a1.append(arr[i] + arr[i + 1] + arr[i + 2])
	if len(a1) == 0:
		return -1
	else:
		return max(a1)


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	for i in range(len(arr) - 2):
		for j in range(i + 1, len(arr) - 1):
			for k in range(i + 2, len(arr)):
				if arr[j] + arr[k] > arr[i]:
					return arr[i] + arr[j] + arr[k]
					break
	else:
		return -1


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	if n < 3:
		return -1
	per = -1
	for i in range(n - 2):
		if arr[i] < arr[i + 1] + arr[i + 2]:
			per = max(per, arr[i] + arr[i + 1] + arr[i + 2])
	return per


def maxPerimeter(arr, n):
	arr.sort(reverse=True)
	for i in range(0, n - 2):
		if arr[i] < arr[i + 1] + arr[i + 2]:
			return arr[i] + arr[i + 1] + arr[i + 2]
	return -1
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	print(maxPerimeter(arr, n))


def maxPerimeter(arr, n):
	arr.sort()
	j = n - 1
	while j - 2 >= 0:
		if arr[j] >= arr[j - 1] + arr[j - 2]:
			j -= 1
			continue
		else:
			return arr[j] + arr[j - 1] + arr[j - 2]
		j -= 1
	return -1
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	print(maxPerimeter(arr, n))


def maxPerimeter(arr, n):
	arr.sort()
	per = -1
	i = n - 3
	while i >= 0:
		if arr[i] + arr[i + 1] > arr[i + 2]:
			per = arr[i] + arr[i + 1] + arr[i + 2]
			break
		i -= 1
	return per
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	print(maxPerimeter(arr, n))


def maxPerimeter(arr, n):
	arr.sort()
	itr = n - 1
	while itr >= 2:
		if arr[itr - 2] + arr[itr - 1] > arr[itr]:
			return arr[itr] + arr[itr - 1] + arr[itr - 2]
		itr -= 1
	return -1
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	print(maxPerimeter(arr, n))


def maxPerimeter(arr, n):
	ans = 0
	arr.sort(reverse=True)
	for i in range(n - 2):
		s3 = arr[i]
		s2 = arr[i + 1]
		s1 = arr[i + 2]
		if s3 < s2 + s1:
			ans = s3 + s2 + s1
			return ans
	return -1


def maxPerimeter(arr, n):
	per = 0
	arr.sort()
	i = n - 3
	while i >= 0:
		if arr[i + 2] < arr[i] + arr[i + 1]:
			per += arr[i] + arr[i + 1] + arr[i + 2]
			return per
		i -= 1
	return -1


def maxPerimeter(arr, n):
	arr.sort()
	if len(arr) < 3:
		return -1
	for i in range(n - 2, 0, -1):
		max = arr[i + 1]
		if max < arr[i] + arr[i - 1]:
			return max + arr[i] + arr[i - 1]
	return -1


def maxPerimeter(arr, n):
	arr.sort()
	maxi = -1
	for i in range(n - 3, -1, -1):
		if arr[i + 2] < arr[i + 1] + arr[i]:
			return arr[i + 2] + arr[i + 1] + arr[i]
	return maxi


def maxPerimeter(arr, n):
	arr.sort()
	max_p = -1
	i = 0
	while i < len(arr) - 2:
		if arr[i] + arr[i + 1] > arr[i + 2]:
			p = arr[i] + arr[i + 1] + arr[i + 2]
			max_p = max(p, max_p)
		i += 1
	return max_p


def maxPerimeter(arr, n):
	arr.sort()
	i = n - 1
	while i >= 2:
		if arr[i - 1] + arr[i - 2] > arr[i]:
			return arr[i] + arr[i - 1] + arr[i - 2]
		i -= 1
	return -1