Source: Highest Product

Given an array A, of N integers A.

Return the highest product possible by multiplying 3 numbers from the array.

NOTE: Solution will fit in a 32-bit signed integer.

Input Format:

The first and the only argument is an integer array A.

Output Format:

Return the highest possible product.

Constraints:

1 <= N <= 5e5

Example:

Input 1:
A = [1, 2, 3, 4]
Output 1:
24

Explanation 1:
2 * 3 * 4 = 24

Input 2:
A = [0, -1, 3, 100, 70, 50]
Output 2:
350000

Explanation 2:
70 * 50 * 100 = 350000

解題：

  1. 這題如果只有正數的話其實相當單純，就是用個迴圈歷遍所有元素值，把最大的三個正數值另外存起來，並隨迴圈推進來持續執行比較更新。但如果輸入值包含負數值呢？
  2. 針對負數值的處理，需要考慮到幾個狀況：
    1. 兩個負數值搭配一個正數值 — 在這狀況下可以對負數值用 abs() 取絕對值，而因為兩負數相乘為正數，故負數值越小，就越符合題目的要求；
    2. 兩個正數值搭配一個負數值或三個負數值 — 在這狀況因為相乘後必為負數，故在解題時會希望不管是正數或負數都是找愈逼近 0 的值愈好
  3. 有了上面這兩層的認知後，可以建立三個陣列來儲存解題必要的資訊：
    A – 在解題時用一個陣列存最大前三個正數，而只要這個陣列可以湊滿三個正數，我們在解題時就完全不用再考慮選一個負數或是選三個負數的選項了（因為相乘取得的數值必定比選奇數個負數的組合還要大）；而針對負數，我們可以另外建兩個陣列：
    B – 一個取最小兩個負數值（取絕對值後最大）；
    C – 另一個則存最大的前三個負數值（三個負數值相乘後為該輸入陣列內所有可能的負數值組合中之最大）；
  4. 而迴圈跑完後，因為前面用的三個資料陣列各自存取各自的內容，彼此互相並未進行比較及干涉，故此時我們需要另外用幾個 if 判斷式來進行檢查：
    1. 檢查存正數值的陣列 (A) 長度是否為 0 （表示最大乘積為陣列 (C) 三個元素值相乘）；
    2. 檢查存正數值的陣列 (A) 長度是否為 1 （表示最大乘積必為該正數乘上陣列 (B) 的兩個元素值）；
    3. 存正數值的陣列 (A) 長度是否大於 1 且存最小負數值的陣列 (B) 長度是否為 2 （表示我們可以取用兩個負數進行相乘），如通過則檢視這兩個值之乘積是否大於陣列 A 的末兩正數值乘積
    4. 上述三個判斷式如都不適用，則表示可直接取用陣列 (A) 之乘積。

Code:

class Solution:
    # @param A : list of integers
    # @return an integer
    def maxp3(self, A):
        maxPos, minNeg = [], []
        n = len(A)
        if n < 3: return 
        elif n == 3: return A[0]*A[1]*A[2]
        minPro = []
        for i in A:
            if i >= 0:
                if len(maxPos) < 3:
                    maxPos.append(i)
                else:
                    maxPos.sort()
                    if maxPos[0] < i:
                        maxPos[0] = i
            else:
                if len(minNeg) < 2:
                    minNeg.append(i)
                else:
                    minNeg.sort()
                    if minNeg[-1] > i:
                        minNeg[-1] = i
                if len(minPro) < 3:
                    minPro.append(i)
                else:
                    minPro.sort()
                    if abs(i) < minPro[0]:
                        minPro[0] = i
        products = sorted(maxPos)
        #condition: 3 neg
        if len(products) == 0:
            products = minPro
        #condition: 2 Neg, 1 Pos
        elif len(products)==1:
            products += minNeg
        #condition: 3 pos or (2 Neg, 1 Pos)
        elif len(products) > 1 and len(minNeg) == 2:
            if minNeg[0]*minNeg[1] > products[0]*products[1]:
                return max(products) * minNeg[0]*minNeg[1]
        #condition: 2 pos 1 neg, only happened when there are only 3 elements
        #covered with if (n == 3) condition
        #should only consider 0
        products.sort(reverse = True)
        return products[0] * products[1] * products[2]

GitHub: GitHub

發表留言