在 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

