We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Since A is first sorted, A[i+2], A[i+1], A[i] are the largest consecutive values which can form triangle. Any other choice won't fulfill the conditions mentioned in the problem statement. I'll prove it by contradiction.
Suppose a, c, r be three non-consecutive values chosen to form the triangle such that a <= c <= r. Here, r is the longest side for the triangle. Now, let the consecutive values keeping r as maximum be p, q, r such that p <= q <= r.
Now, since a, c, r form non-degenerate triangle, a+c > r (by triangle inequality). Also, p+q >= a+c because p, q, r are consecutive. So p+q >= a+c > r, which implies p+q > r. Thus, a non-degenerate triangle can be formed using p, q, r too !
Finally, comparing perimeters : p+q+r >= a+c+r since p+q >= a+c. This contradicts our choice for maximum perimeter. Hence, choose the consecutive values.
Maximum Perimeter Triangle
You are viewing a single comment's thread. Return to all comments →
Since A is first sorted, A[i+2], A[i+1], A[i] are the largest consecutive values which can form triangle. Any other choice won't fulfill the conditions mentioned in the problem statement. I'll prove it by contradiction.
Suppose a, c, r be three non-consecutive values chosen to form the triangle such that a <= c <= r. Here, r is the longest side for the triangle. Now, let the consecutive values keeping r as maximum be p, q, r such that p <= q <= r.
Now, since a, c, r form non-degenerate triangle, a+c > r (by triangle inequality). Also, p+q >= a+c because p, q, r are consecutive. So p+q >= a+c > r, which implies p+q > r. Thus, a non-degenerate triangle can be formed using p, q, r too !
Finally, comparing perimeters : p+q+r >= a+c+r since p+q >= a+c. This contradicts our choice for maximum perimeter. Hence, choose the consecutive values.