効率最適化

Question

-1000〜1000の範囲の1〜50の整数で構成されるリストが与えられている場合、与えられたリスト内の1つまたは任意の数の整数の最大積を計算します。

私のアプローチ：

import itertools 

def answer(xs): 
    cur = 1 
    dal = [] 
    for i in range(len(xs), 0, -1): 
     for j in itertools.combinations(xs, i): 
      for x in j: 
       cur *= x 
      dal.append(cur) 
      cur = 1 
    dal.sort(reverse=True) 
    return str(dal[0]) 

結果がタイムアウトしました。私はプロシージャの構造をできるだけ効率的にするために最適化したい。

Answer 1

負の数が負である場合（ゼロに最も近い）、他のすべてを掛ける場合は、すべての整数を掛けて最大の積を得ることができます。 n = 1の場合は、そのまま番号を印刷します。

編集：その後、

if len(mylist)==1: 
    print mylist[0] 
else: 
    count=0 
    for i in mylist: 
     if i<0: 
      count+=1 
    if count>0: 
     mylist.sort() 
     if mylist[-1]==0: 
      print "0" 
     else: 
      ans=1 
      flag=1 
      for i in xrange(len(mylist)): 
       if mylist[i]>0 and flag==1: 
        ans/=mylist[i-1] 
       else: 
        ans*=mylist[i] 
      if flag==1: 
       ans/=mylist[-1] 
      print ans 
    else: 
     ans=1 
     for i in mylist: 
      if i>0: 
       ans*=i 
     print ans 

とあなたの関数からANSを返します。

これはO（n）ソリューションです。

Answer 2

これは、いくつかの方法で最適化できます。まず、配列内のすべてをホストするのではなく、変数maximumをxs[0]に初期化し、各製品をチェックします。さらに、乗算を自分で行うのではなく、operatorモジュールのmulをreduceで使うことができます。最後に、私はこれがあなたのコードになるだろう、それはrangeよりも、それをより効率的に配列を作成しませんPythonの2のようにxrangeを使用することになり、このよう

from itertools import combinations 
from operator import mul  

def answer(xs): 
    maximum = xs[0] 
    one = 1 in xs 
    filter(lambda a: a != 0 and a != 1, xs) 
    if len(xs) == 0: 
     if one: 
      return 1 
     else: 
      return 0 
    for i in xrange(len(xs), 0, -1): 
     for j in combinations(xs, i): 
      prod = reduce(mul, j, 1) 
      if prod > maximum: 
       maximum = prod 
    return str(maximum) 

を見て、私はstr(maximum)として復帰を残していますが、としてそれを返すことができますmaximumこれは整数です。

Answer 3

計算に数か月を要する場合を除き、すべての組み合わせを実行することは悪い考えです。すべての数字が肯定的だった場合は、それらをすべて掛け合わせるだけです。もしすべてが否定的だったらあなたはそれらの数を取るでしょう。スキップしなければならない場合は、最大値をスキップします（-2は-5より大きい）。ミックスにゼロを追加すると、常にゼロが返されます。これは、前のいずれの場合よりも悪いです。正の数がなく、0または1つの負の数がある場合は、あなたが持っている最大の数を取ってください。それはゼロか唯一の負の数です。

def answer(xs):  
    mult = 1 
    valid = 0 

    for i in xs: 
     if i > 0: 
      mult *= i 
      valid = 1 

    negative = [i for i in xs if i<0] 
    negative.sort() 

    if(len(negative) & 1): 
     del negative[-1] 

    for i in negative: 
      mult *= i 
      valid = 1 

    if valid==0: 
     return max(xs) 

    return mult 

、ここではいくつかのテストケースです：

xs = [0] 
print(xs,"->",answer(xs)) #[0] -> 0 
xs = [-1] 
print(xs,"->",answer(xs)) #[-1] -> -1 
xs = [0,-1] 
print(xs,"->",answer(xs)) #[0, -1] -> 0 
xs = [-2,-3] 
print(xs,"->",answer(xs)) #[-2, -3] -> 6 
xs = [-2,-3,-4] 
print(xs,"->",answer(xs)) #[-2, -3, -4] -> 12 
xs = [-2,-3,0] 
print(xs,"->",answer(xs)) #[-2, -3, 0] -> 6 
xs = [-2,3] 
print(xs,"->",answer(xs)) #[-2, 3] -> 3 

Answer 4

あなたはO（n）の時間計算のための二相のアルゴリズムを使用することができます。最初にすべての正の数にお互いを掛け、正の数がない場合には最大のものを選んでください。 reduceでは、これは簡単に1行で行うことができます。

次の手順では、すべての負の数を除外します。複数のものがある場合は、それらを一緒に掛け合わせます。乗算の結果が負の数（=負の数が奇数の場合）の結果は、負の数の最大値で除算されます。次に、ステップ1で得た製品にステップ2の製品を掛けて最終結果を得ます。ステップ1の生成物が非正数である場合、ステップ2の生成物が結果である。

from functools import reduce 

nums = [3, -4, 5, -2, -3, 0, 1] 
res = reduce(lambda x,y: x * y if x > 0 and y > 0 else max(x, y), nums) 
negatives = [x for x in nums if x < 0] 
if len(negatives) > 1: 
    neg = reduce(lambda x,y: x * y, negatives) 
    if neg < 0: 
     neg //= max(negatives) 
    res = max(res, 1) * neg 

print(res) 

出力：

180 

あなたはPythonの2を使用している場合、それは普通のものを使用して組み込みの代わりに、floordivのだからreduceをインポートする必要はありません。