CODEWITHSUNDEEP
c++algorithmdynamic-programming
Jonathan Barker
Jonathan Barker

Reputation: 21

Finding maximum value of products and sum and subtract and division for elements in array

Hi i have following problem which i want to implement:

I have two arrays n integers array and n - 1 operations array

numbers array is fixed while the operator array can be used in any permutation in order to get the maximum value (Thank you @grek40)

example 1:

given array of integers: 1 2 7 5 1 2 and array of operations: + + + + *

I want to find maximum adjacent product sum subtract division i.e. 1+2+7*5+1+2 = 41

example 2:

given array of integers: 1 3 5 6 9 10 12 14 and array of operations: + + * * - / /

I want to find maximum adjacent product sum subtract division i.e. 1-3/5/6+9+10*12*14 = 1689.9

I am beginner in dynamic programming. I am unable to figure out the recurrence relation for the following problem.

Can anyone please suggest something?

thanks!

I try to use Enumeration methods, Time complexity is n!

for operators in allOperators:
    op = list(operators)
    op.append(' ')
    operation = ""

    for i, number in enumerate(inputNumbers):
        count += 1
        operation += number + op[i]
    output = eval(operation)

    if output > maxOutput:
        maxOutput = output

Upvotes: 2

Views: 1178

Answers (2)

akshay dhule
akshay dhule

Reputation: 167

You can follow similar approach as this question :

Given a list of integer numbers, a list of symbols [+,-,*,/] and a target number N ,

Only difference is it talks about matching the number N, You can find Maximum sum.

The idea here is to generate combinations of the operators as long as the length of the array.

  1. You can use Hashmap to store operator and count. That way while building your expression, you can keep track of count for each operator. map<operator, count>
  2. Write separate Function to solve the expression. Getresult(expression)
  3. Calculate all combination using numbers and operators using std::next_permutation:
  4. Iterate through list of numbers :
  5. Get result for each expression
  6. Track current_max , and expression_max for max.
  7. Finally Return current_max and expression_max

Upvotes: 0

obgnaw
obgnaw

Reputation: 3037

Code will better than word for this problem.The state transition equation is clear in the code.

import functools
test1 = (1, 2, 7, 5, 1, 2)
test2 = (1, 3, 5, 6 ,9 ,10, 12, 14)
@functools.lru_cache()
def BaseSolution(nums, add, sub, mul, div, length):
    if  add<0 or sub<0 or mul<0 or div<0 or length<0:
         return float("-inf")
    if  length == 0:
        return nums[length]
    else:
        return max(
            BaseSolution(nums, add-1, sub, mul, div, length-1) + nums[length],
            BaseSolution(nums, add, sub-1, mul, div, length-1) - nums[length],
            MulOrDivSolution(nums, add, sub, mul-1, div, length-1, '*'+str(nums[length])),
            MulOrDivSolution(nums, add, sub, mul, div-1, length-1, '/'+str(nums[length])),
            )
def MulOrDivSolution(nums, add, sub, mul, div, length, lzayVal):
    if  add<0 or sub<0 or mul<0 or div<0 or length<0:
         return float("-inf")
    if  length == 0:
        return eval( str(nums[length])+lzayVal)
    else:   
        return max(
            BaseSolution(nums, add-1, sub, mul, div, length-1) + eval( str(nums[length])+lzayVal),
            BaseSolution(nums, add, sub-1, mul, div, length-1) - eval( str(nums[length])+lzayVal),
            MulOrDivSolution(nums, add, sub, mul-1, div, length-1, '*'+str(nums[length])+lzayVal),
            MulOrDivSolution(nums, add, sub, mul, div-1, length-1, '/'+str(nums[length])+lzayVal),
            )
if __name__ == '__main__':
    print(BaseSolution(test1,4,0,0,1,5))
    print(BaseSolution(test2,2,1,2,2,7))

Upvotes: 1

Related Questions