CODEWITHSUNDEEP
pythonpython-3.xalgorithmbig-obiginteger
Son Ha Nguyen
Son Ha Nguyen

Reputation: 45

Find max product of 2 subarray split from 1 array

I have a problem.

Give an arr array of integers. Let's divide this array into 2 consecutive subarrays so that the sum of the product of the products in these two arrays is the greatest. Since the result can be very large, it will be divided by a remainder of 10^9+7

[Input] array of integers 2 <= arr.length <= 10^4. |arr[i]| <= 10^4.

For example:

Explanation: we can divide into two sub arrays [2] and [4,1,3].

Explanation: we can divide into two sub arrays [-1,3] and [4, -2]

Here's my solution:


    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

However, it can be handle the big number. I am looking for efficient solution.

Upvotes: 1

Views: 747

Answers (2)

Ignacio Alorre
Ignacio Alorre

Reputation: 7605

You can solve the problem in this way.

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

Upvotes: 0

Abhinav Mathur
Abhinav Mathur

Reputation: 8101

Your code has a time complexity of O(N^2), which needs to be reduced.
Consider an array product, where product[i] = arr[0]*arr[1]....*arr[i]. This array can be computed in O(N) with one pass. Now, you need to split your array in two consecutive parts. Let's consider the subarrays to be arr[0 to i-1] and arr[i:], for a given i. We can loop from i=n-2 to i=1, and see where we get the maximum sum.

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)

Upvotes: 1

Related Questions