在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):sum = 12,(3 6 10):sum = 19,(3 4 10):总和= 17,(4 5 10):总和= 19,(2 5 10):总和= 17,因此最大值为19

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

  • n:= A的大小

  • res:= 0

  • 对于1到n-1范围内的i

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

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

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

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

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

    • first_max:= 0,second_max:= 0

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

    • 对于范围i +1至n的j,执行

    • 如果first_max和second_max不为零,则

    • 返回资源

    示例

    让我们看下面的实现以更好地理解-

    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

    以上是 在Python中查找数组中三元组的最大和,例如i <j <k和a [i] <a [j] <a [k] 的全部内容, 来源链接: utcz.com/z/352530.html

    回到顶部