在 Python 中查找数组中三元组的最大和,例如 i < j < k 和 a[i] < a[j] < a[k]

pythonserver side programmingprogramming更新于 2025/10/10 18:20:17

假设我们有一个正数数组,该数组中有 n 个元素,我们必须 查找三元组 (ai + aj + ak ) 的最大和,使得 0 <= i < j < k < n 且 ai< aj< ak。

因此,如果输入为 A = [3,6,4,2,5,10],则输出将为 19,因为三元组为 (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。所以最大值为 19

为了解决这个问题,我们将遵循以下步骤 −

  • n := A 的大小

  • res := 0

  • 对于范围为 1 到 n - 1 的 i,执行

    • first_max := 0, second_max := 0

    • 对于 j 在 0 到 i 的范围内,执行

      • 如果 A[j] < A[i],则

        • first_max := first_max 的最大值,A[j]

    • 对于 j 在 i + 1 到 n 的范围内,执行

      • 如果 A[j] > A[i],则

        • second_max := second_max 的最大值,A[j]

    • 如果 first_max 且 second_max 非零,则

      • res := res 的最大值,first_max + A[i] + second_max

  • 返回 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

相关文章


有用资源