haskell中3个实现的最高产品

Question

我想在haskell中实现3问题的最高产品的算法.这是问题陈述:

给定一个整数数组,找到可以从三个整数中得到的最高乘积.

例如,给定[1, 2, 3, 4],算法应该返回24.并给出[-10, -10, 5, 1, 6],3的最高产品将是600 = -10*-10*6.

我的尝试(第一次尝试没有否定):

sol2' a b c []     = a*b*c
sol2' a b c (x:xs) = sol2' a' b' c' xs
  where 
    a' = if (x > a) then x else a
    b' = if (x > a && a > b) then a else b
    c' = if (x > a && a > b && b > c) then b else c

sol2 li = sol2' a b c li
  where a = 0
        b = 0 
        c = 0

我测试了实现,[3, 5, 1, 2, 4, 10, 0, 4, 8, 11]但返回值是550,应该是880.

Answer 1

正数

在您寻找最高数字的意义上,您处于正确的轨道上.然而问题是a,b和c并不总是有序的.

事实上,比方说我们有数字[6,2,4].然后(a,b,c)通过递归的方式将演变为:

(0,0,0) -> (6,0,0) -> (2,6,0) -> (4,2,6)

但是现在a=4,这意味着如果我们现在遇到3,我们将不会替换该值,而我们可以这样做,因为我们可以删除2.

虽然有很多方法可以解决这个问题,但最好的方法是保持秩序:确保这样做a <= b <= c.

所以我们可以使用:

sol1 = sol2' (0,0,0)

sol2' (a,b,c) []     = a*b*c
sol2' t@(a,b,c) (x:xs) = sol2' f xs
  where f | x >= c = (b,c,x)
          | x >= b = (b,x,c)
          | x > a = (x,b,c)
          | otherwise = t

这产生了预期的:

Prelude> sol1 [1,2,3,4]
24
Prelude> sol1 [3, 5, 1, 2, 4, 10, 0, 4, 8, 11]
880

Intermezzo:如果存在负数,则跟踪数字

您的程序首先(0,0,0)作为前三个值.但是,例如,如果列表仅包含负数(即[-1,-2,-3]),我们当然希望首先跟踪这些数字.我们可以这样做,例如通过使用列表中的元素初始化我们的元组:

import Data.List(sort)

sol1 (xa:xb:xc:xs) = sol2' (a,b,c) xs
    where [a,b,c] = sort [xa,xb,xc]

所以现在我们采用前三个元素,对它们进行排序,并将它们作为第一个元组.处理剩余的列表.如果sol1没有给出至少包含三个元素的列表,则此函数将出错,但在这种情况下可能没有答案.我们可以使用a Maybe来处理函数非整数这一事实.

所有数字

当然我们也想处理负数.将两个负数相乘得到正数.因此,通过跟踪两个最小的数字,我们可以正确地进行数学运算.首先,我们将使用另一个参数(d,e)来跟踪最小的数字d <= e:

sol1_all = sol2_all' (0,0,0) (0,0)

sol2_all' (a,b,c) (d,e) []     = -- ...
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
  where f | x >= c = (b,c,x)
          | x >= b = (b,x,c)
          | x > a = (x,b,c)
          | otherwise = t
        g | x <= d = (x,d)
          | x <= e = (d,x)
          | otherwise = u

所以现在我们已经获得了最多的数字(a,b,c)和最小的数字(d,e).如果d并且e确实是否定的,那么产生大的唯一方法.所以现在我们有以下可能性来考虑a*b*c和c*d*e.所以我们可以把它写成:

sol2_all' (a,b,c) (d,e) [] = max (a*b*c) (c*d*e)
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
  where f | x >= c = (b,c,x)
          | x >= b = (b,x,c)
          | x > a = (x,b,c)
          | otherwise = t
        g | x <= d = (x,d)
          | x <= e = (d,x)
          | otherwise = u

但请注意,这并不总是会产生正确的结果,因为我们可以计算两个元组中的两个数字.我们可以通过正确 初始化元组来解决这个问题:

import Data.List(sort)

sol1_all (xa:xb:xc:xs) = sol2_all' (a,b,c) (a,b) xs
    where [a,b,c] = sort [xa,xb,xc]

sol2_all' (a,b,c) (d,e) [] = max (a*b*c) (c*d*e)
sol2_all' t@(a,b,c) u@(d,e) (x:xs) = sol2_all' f g xs
  where f | x >= c = (b,c,x)
          | x >= b = (b,x,c)
          | x > a = (x,b,c)
          | otherwise = t
        g | x <= d = (x,d)
          | x <= e = (d,x)
          | otherwise = u

选择不同(可能等同)元素背后的基本原理

我们怎么知道我们不会两次使用元素？由于我们只使用a*b*c或c*d*e在具有三个元素的名单的情况- -这将归结为max(a*b*c,a*b*c)(a,b,和c这里的结果sort).所以保证了独特性.因为我们只会在第一个元组中添加元素,如果这些元素至少大于a且小于b,我们知道为了x在两个元组中添加一个元素,它应该是a <= x <= b.在那种情况下,我们将获得元组(x,b,c)和(a,x).但由于我们在这种情况下,评估x*b*c和a*x*c,x因此不进行任何表情发生了两次.

Leetcode挑战

我向Leetcode Challenge提交了此代码的Python版本并被接受:

class Solution:
    def maximumProduct(self, nums):
        a,b,c = d,e,_ = sorted(nums[:3])
        for x in nums[3:]:
            if x >= c:
                a,b,c = b,c,x
            elif x >= b:
                a,b = b,x
            elif x >= a:
                a = x
            if x <= d:
                d,e = x,d
            elif x < e:
                e = x
        return max(a*b*c,c*d*e)