Array A contains the elements, \$A_1,A_2, \ldots, A_N\$.
And array B contains the elements, \$B_1,B_2, \ldots, B_N\$.There is a relationship between \$A_i\$ and \$B_i\$: any element \$A_i\$ lies between \$1\$ and \$B_i\$.
Let the cost S of an array A be defined as:
$$ S = \sum_{i=2}^N \lvert A_i - A_{i-1} \rvert$$
Given B, find and print the largest possible value of S.
The problem can be found here
Example:
size of array
:5
array
: 10 1 10 1 10
output
: 36
(since the max value can be derived as |10 - 1| + |1 - 10| + |10 - 1| + |1 - 10|)
Approach:
The only approach I could think of was brute force. I thought I would make an overlapping recursive equation so that I could memoize it, but was not able to.
CODE:
public static void func(int pos,int[] arr,int[] aux,int n)
{
/*
* pos is current index in the arr
* arr is array
* aux is temp array which will store one possible combination.
* n is size of the array.
* */
//if reached at the end, check the summation of differences
if(pos == n)
{
long sum = 0;
for(int i = 1 ; i < n ; i++)
{
//System.out.print("i = " + i + ", arr[i] = " + aux[i] + " ");
sum += Math.abs(aux[i] - aux[i - 1]);
}
//System.out.println();
//System.out.println("sum = " + sum);
if(sum > max)
{
max = sum;
}
return;
}
//else try every combination possible.
for(int i = 1 ; i <= arr[pos] ; i++)
{
aux[pos] = i;
func(pos + 1,arr,aux,n);
}
}
NOTE:
The complexity of this is \$\mathcal{O}(n*2^n)\$