Dynamic programming of finding the maximum value of products and the sum for elements in an array
Hi I have the following problem that I want to implement:
a given array of integers: 1 2 7 5 1 2
I want to find the maximum contiguous sum of a product, i.e.1+2+(5*7)+1+2 = 41
a given array of integers: 1 2 4 2 4 2 I want to find the maximum contiguous sum of a product i.e. 1+(2*4)+(2*4)+2 = 19
The limitation with multiplication is that only one adjacent element can be used for multiplication. those. if in an array 2 4 2
we calculate it as 2+(4*2) or (2*4)+2
.
I am starting to programming dynamically. I am unable to define the repetition relation for the next problem.
Can anyone suggest something?
source to share
A step-by-step solution looks like this:
- consider the first element, it is maximum when there is no other element.
- until your whole item exists.
- add i'th element:
- F (i) = Max {F (i-1) + e i, f (i-2) + e i-1 * e yasub>)
where F (i) is your maximum for the first i elements and e i 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
andF(1) + 2 * 4= 1 + 2 * 4
, so this isF(3) = 1+2*4 = 9
. - then you have
F(2) + 4 * 3 = 1 + 2 + 4 * 3
uF(3) + 3 = 1 + 2 * 4 + 3
, so thisF(4) = 1 + 2+ 4*3 = 15
- then you have
F(4) + 4 = 1 + 2 + 4 * 3 + 4
uF(3) + 3*4 = 1 + 2 * 4 + 3 * 4
, so thisF(5) = 1 + 2 * 4 + 3 * 4 = 21
source to share
I am posting a 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]);
}
}
source to share