효율 최적화

Question

-1000에서 1000 사이의 범위에 1에서 50까지의 정수로 구성된 목록이 주어지면 주어진 목록에서 하나 또는 임의의 수의 정수의 최대 곱을 계산하십시오.

내 방식 :

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

음수가 다른 경우에도 최대 정수가 음수 (0에 가장 가깝게)로 남고 다른 모든 곱하기 정수를 곱하여 최대 곱을 얻을 수 있습니다. (n = 1 인 경우) 그대로 번호를 인쇄하십시오. 반환 ANS 함수에서 다음

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 

과 :

편집.

이것은 O (n) 솔루션입니다.

Answer 2

몇 가지 방법으로 최적화 할 수 있습니다. 먼저 배열의 모든 것을 호스팅하는 대신 변수 maximum을 xs[0]으로 초기화하고 각 제품을 검사합니다. 또한, 곱셈을 직접하는 대신, operator 모듈의 mul을 reduce와 함께 사용할 수 있습니다. 마지막으로, 나는이 만들 것 range 것보다 더 효율적 배열을 만들지 않습니다 파이썬이 그와 같이 xrange 사용하는 것이 내가 str(maximum)로 수익을 왼쪽,하지만 당신은 그것을 반환 할 수 있습니다이

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) 

같은 코드 모양 maximum 원하는 경우 정수입니다.

Answer 3

계산을 위해 개월이 없으면 모든 조합을 검토하는 것은 좋지 않습니다. 모든 숫자가 양수이면 모두 곱하면됩니다. 모두가 부정적인 경우에 당신은 그 (것)들의 수를 가지고 갈 것입니다. 건너 뛰려면 가장 큰 것을 건너 뛰십시오 (-2는 -5보다 큽니다). 믹스에 0을 추가하면 항상 이전의 모든 경우보다 나빠진 0이 반환됩니다. 양수가없고 0 또는 음수가 있으면 가장 큰 숫자를 취하십시오. 그것은 0 일 수도 있고, 음수 일 수도 있습니다.

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)이 시간 복잡도에 대한 2 단계 알고리즘을 사용할 수 있습니다. 먼저 모든 양수를 서로 곱하십시오. 양수가없는 경우 가장 큰 것을 선택하십시오. reduce을 사용하면이 작업을 한 줄로 쉽게 수행 할 수 있습니다.

다음 단계에서 모든 음수를 필터링하십시오. 둘 이상이있는 경우 모두 함께 곱하십시오. 곱셈 결과가 음수 (= 음수가 홀수 인 경우)의 결과를 음수의 최대 값으로 나눕니다. 그런 다음 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 

당신이 내장되어있어 대신 floordiv의 그냥 일반 하나를 사용하기 때문에 reduce를 가져올 필요가 없습니다 파이썬이 사용하는 경우.