Tìm tổng lớn nhất của các bộ ba trong một mảng như i

Giả sử chúng ta có một mảng các số dương, có n phần tử trong mảng đó, chúng ta phải tìm tổng lớn nhất của bộ ba (ai + aj + ak) sao cho 0 <=i

Vì vậy, nếu đầu vào là A =[3,6,4,2,5,10], thì đầu ra sẽ là 19 vì các bộ ba là (3 4 5):sum =12, (3 6 10):sum =19, (3 4 10):sum =17, (4 5 10):sum =19, (2 5 10):sum =17. Vậy giá trị lớn nhất là 19

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• res:=0

• đối với tôi trong phạm vi từ 1 đến n - 1, hãy thực hiện

  • first_max:=0, second_max:=0

  • đối với j trong phạm vi 0 đến i, thực hiện

    • nếu A [j]

      • first_max:=tối đa của first_max, A [j]

  • đối với j trong phạm vi i + 1 đến n, thực hiện

    • nếu A [j]> A [i], thì

      • second_max:=tối đa second_max, A [j]

  • nếu first_max và second_max khác 0 thì

    • res:=tối đa res, first_max + A [i] + second_max

• trả lại 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