Блог

У меня есть проблема.

Укажите arr массив целых чисел. Давайте разделим этот массив на 2 последовательных подмассива так, чтобы сумма произведения произведений в этих двух массивах была наибольшей. Поскольку результат может быть очень большим, он будет разделен на остаток 10^9 7

[Ввод] массив целых 2 <= arr.length <= 10^4 чисел. |arr[i]| <= 10^4 .

Например:

• На arr = [2,4,1,3] то maxProduct(arr) = 14 время .

Пояснение: мы можем разделить на два подмассива [2] и [4,1,3] .

• На arr = [-1,3,4, -2] то maxProduct (arr) = -11 время .

Пояснение: мы можем разделить на два подмассива [-1,3] и [4, -2]

Вот мое решение:

 
    def mul(arr):
        r = 1
        for i in arr:
            r*=i
        return r
    
    def maxProduct(arr):
        res_max = mul(arr[0:1])  mul(arr[1:])
        for i in range(1,len(arr)):
            first_half = arr[0:i]
            after_half = arr[i:]
            t = mul(first_half)   mul(after_half)
            if res_max<t:res_max=t
        return res_max

 

Тем не менее, это может быть обработано большим числом.
Я ищу эффективное решение.

Ваш код имеет временную сложность O(N^2) , которую необходимо уменьшить.
Рассмотрим массив product , где product[i] = arr[0]*arr[1]....*arr[i] . Этот массив может быть вычислен за O(N) один проход. Теперь вам нужно разделить ваш массив на две последовательные части. Давайте рассмотрим подмассивы arr[0 to i-1] как и arr[i:] , для данного i . Мы можем выполнить цикл от i=n-2 до i=1 и посмотреть, где мы получим максимальную сумму.

 mod = int(1e9) 7
arr = [2,4,1,3]
n = len(arr)
product_array = [0]*n
product_array[0] = arr[0]

for i in range(1,n):
    product_array[i] = product_array[i-1]*arr[i]

ans = float("-inf")
right_product = arr[n-1]
left_product = product_array[n-2]
ans = left_product right_product

for i in range(n-2,0,-1):
    right_product = right_product*arr[i]
    left_product = product_array[i-1]
    curr_sum = left_product right_product
    ans = max(ans, curr_sum)

print(ans%mod)
 

Вы можете решить проблему таким образом.

 import numpy as np

def get_max_product(a):
    # Defining initial conditions to beat
    maxv = sum([np.prod(a[:1]),np.prod(a[1:])])
    best_i = 1
    # Iterating the array trying to beat the initial conditions
    for i in range(2,len(a)):
        sumprod = sum([np.prod(a[:i]),np.prod(a[i:])])
        # Updating best scenario in a better one found
        if sumprod > maxv:
            maxv,best_i = sumprod,i
    
    return a[:best_i],a[best_i:]

get_max_product([2,4,1,3])