Codility每周一课：L6 Sorting(P6.2)

0.png

P6.2 MaxProductOfThree
Maximize for any triplet (P, Q, R).

• P6.2 三个数的最大乘积
  三元组(P, Q, R)对应的A[P] * A[Q] * A[R]的最大值

由N个整数组成的非空数组A。三元组(P, Q, R)的乘积等于A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N)。

例如，数组A如下： A[0]=-3，A[1]=1，A[2]=2，A[3]=-2，A[4]=5，A[5]=6

下面只给出3个三元组的示例：

（0，1，2），乘积是−312=−6
（1，2，4），乘积为125=10
（2，4，5），乘积为256=60

目的是找到所有的三元组的最大乘积。

编写函数：

def solution(A)

给定一个非空数组A，则返回三元组的最大乘积的值。

例如，对于上面的示例，函数应该返回60，因为三元组（2，4，5）的乘积最大。

假定：

1. N是区间[3，100000]内的整数；
2. 数组A的每个元素都是区间[-1000，1000]内的整数。

• 解题思路

其实只要数组中的元素个数不小于4个，并且最大的数为非负数，那么最终的乘积都是非负数，因此对数组进行排列。只要比较前面三个正值和最后面的两负以及前面的一正的乘积哪个大即可。如果均为负数，则排列后的前三个值的乘积为最大的。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 6：Sorting
# P 6.2 MaxProductOfThree


def solution(A):
    """
    返回数组A中所有三元组对应的乘积的最大值,时间复杂度O(N * log(N))
    :param A: 整数数组
    :return: 乘积最大值
    """
    if len(A) == 3:
        return A[0] * A[1] * A[2]
    else:
        A.sort(reverse=True)
        if A[0] <= 0:
            return A[0] * A[1] * A[2]
        else:
            return max([A[0] * A[1] * A[2], A[0] * A[-1] * A[-2]])

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image