CODEWITHSUNDEEP
algorithmdynamic-programming
mribot
mribot

Reputation: 529

Dynamic programming finding maximum value of products and sum for elements in array

Hi i have following problem which i want to implement:

given array of integers: 1 2 7 5 1 2 I want to find maximum adjacent product sum i.e. 1+2+(5*7)+1+2 = 41

given array of integers: 1 2 4 2 4 2 I want to find maximum adjacent product sum i.e. 1+(2*4)+(2*4)+2 = 19

Constraint on multiplication is that only one adjacent element can be used for multiplication. i.e. if we have 2 4 2 in array we will compute it as 2+(4*2) or (2*4)+2.

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

Can anyone please suggest something?

Upvotes: 5

Views: 7703

Answers (2)

Raja Jain
Raja Jain

Reputation: 41

I am posting complete java solution for this problem. Added inline comments for the implemented logic.

public class MaxValueOfRagularExpression {

    public static void main(String[] args) {
        int size=6;
        int arr[] = new int[size];

        arr[0]=2;
        arr[1]=1;
        arr[2]=1;
        arr[3]=1;
        arr[4]=1;
        arr[5]=2;

        // array elements are as follows :
        // A0     A1    A2      A3    A4     A5
        // 2      1      1      1     1      2

        int sol[] = new int[size];
        sol[0]=arr[0];
        for(int i = 1;i<size;i++){
            // sol[i] would contain the optimized value so far calculated.
            for(int k = 0;k<i ;k++) {
                // for each k , find sum of all array elements  i.e. k+1<=j<=i
                // and then calculate max of (sol[k] + sum or sum[k] * k )
                int sum =0;
                for (int j = k+1; j <= i; j++) {
                    sum += arr[j];
                }
                sol[i] = Math.max(Math.max(sol[i],(sol[k] + sum)), sol[k]*sum);
            }
        }
        // after processing above block , the sol array will look like :
        //SOL[0]  SOL[2]   SOL[2]   SOL[3]   SOL[4]   SOL[5]
        // 2        3       4        6          9     18
        System.out.println(sol[size-1]);
    }
}

Upvotes: 1

Lrrr
Lrrr

Reputation: 4805

Step by step solution is like this :

  • consider first element, it is maximum when there is no other element.
  • while your all element are not there continue.
  • add i'th element:
    • F(i) = Max{F(i-1) + ei , f(i-2) + ei-1 * ei)

where F(i) is your max for first i elements and ei is your i'th element.

Consider this : 1 2 4 3 4

  • first we have F(1) = 1.
  • then F(2) = 1 + 2 .
  • then we compare F(2) + 4 = 1 + 2 + 4 and F(1) + 2 * 4= 1 + 2 * 4 so it is F(3) = 1+2*4 = 9.
  • then you have F(2) + 4 * 3 = 1 + 2 + 4 * 3 and F(3) + 3 = 1 + 2 * 4 + 3 so it is F(4) = 1 + 2+ 4*3 = 15
  • then you have F(4) + 4 = 1 + 2 + 4 * 3 + 4 and F(3) + 3*4 = 1 + 2 * 4 + 3 * 4 so it is F(5) = 1 + 2 * 4 + 3 * 4 = 21

Upvotes: 6

Related Questions