ধরা যাক একটি পজিটিভ নম্বরের অ্যারে আছে যার আকার n। আমাদের সর্বোচ্চ ট্রিপলেট সম (ai + aj + ak) বের করতে হবে যাতে 0 <= i < j < k < n এবং ai < aj < ak।
যেমন, A = [3,6,4,2,5,10] হলে আউটপুট 19, কারণ ট্রিপলেট (3,6,10) এবং (4,5,10) দুটোরই সম 19।
সমাধানের ধাপসমূহ
- n := 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])
- যদি first_max এবং second_max উভয়ই নন-জিরো হয়: res = max(res, first_max + A[i] + second_max)
- return res
উদাহরণ
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))
ইনপুট
[3,6,4,2,5,10]
আউটপুট
19
