在 Python 中查找数组中满足 i < j < k 且 a[i] < a[j] < a[k] 条件的三元组的最大和

假设我们有一个正数数组，其中有 n 个元素，我们必须找到三元组 (ai + aj + ak) 的最大和，条件是 0 <= i < j < k < n 且 ai < aj < ak。

因此，如果输入类似于 A = [3,6,4,2,5,10]，则输出将为 19，因为三元组为 (3 4 5)：和 = 12，(3 6 10)：和 = 19，(3 4 10)：和 = 17，(4 5 10)：和 = 19，(2 5 10)：和 = 17。因此最大值为 19

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

• n := A 的大小

• res := 0

• 对于 i 从 1 到 n - 1，执行：

  • 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

Arnab Chakraborty

更新于：2020年8月25日

423 次浏览

开启你的职业生涯

完成课程获得认证

开始学习