查找从 1 个数组拆分的 2 个子数组的最大积

Question

我有问题。

给出一个 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

但是，它可以处理大数字。我正在寻找有效的解决方案。

Answer 1

您的代码的时间复杂度为 O(N^2)，需要降低。
考虑一个数组 product，其中 product[i] = arr[0]*arr[1]....*arr[i]。这个数组可以在 O(N) 中计算一次。现在，您需要将数组分成两个连续的部分。对于给定的 i，让我们将子数组视为 arr[0 to i-1] 和 arr[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)

Answer 2

你可以这样解决问题。

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])

查找从 1 个数组拆分的 2 个子数组的最大积

Find max product of 2 subarray split from 1 array

python

python-3.x

algorithm

big-o

biginteger