Company: Deutsche_Bank_26nov
Difficulty: medium
Triangle Problem Description An array A consisting of N integers is given. A triplet of indices (P, Q, R) is called a triangle if 0 ≤ P < Q < R < N and: A[P] + A[Q] > A[R] , A[Q] + A[R] > A[P] , A[R] + A[P] > A[Q] . The perimeter of such a triangle equals A[P] + A[Q] + A[R] . Write a function that, given an array A of N integers, returns the maximum perimeter of any triangle in this array. The function should return -1 if there are no triangles. Note that the inequality must hold between the indices P, Q, R, but it is accepted that e.g. A[P] = A[Q] . Examples Example 1: Input: A = [10, 2, 5, 1, 8, 20] Output: 23 Explanation: Triplet (0, 2, 4) is a triangle and its perimeter equals 10 + 5 + 8 = 23. There is no other triangle in this array with a larger perimeter. Example 2: Input: A = [5, 10, 18, 7, 8, 3] Output: 25 Explanation: The triangle with the maximum perimeter is (1, 3, 4), with a perimeter of 10 + 7 + 8 = 25. Example 3: Input: A = [10, 20, 30] Output: -1 Explanation