Find the maximum possible summation of differences of consecutive elements

Question

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)\$

Answer 1

The above can be optimized by using two things.

1. Memorizing the result of the func(). To implement memorizing you need to send some response from the func which can be memorized for certain parameters. In your cases it wouldn't be possible. You need to change the func defination to implement memorizing.

2. Pre-processing on array B to calculate minimum till any i and maximum till any i.

Explaining 2nd point in detail, at any point of three possible combination of \$A_{i-1}, A_i\$ and \$A_{i+1}\$

\$A_i > A_{i-1}, A_{i+1}\$, In this case it makes sense to choose \$A_i\$ as the max value in B till i

\$A_i < A_{i-1},A_{i+1}\$, In this case it makes sense to choose \$A_i\$ as the min value in B till i

\$A_{i-1} < A_i < A_{i+1}\$, In this case you can see \$A_i\$ would have any involvement in final sum. It is getting cancelled out. So even if we choose \$A_{i-1}\$ or \$A_{i+1}\$ as \$A_i\$ it will also give same result. Hence it makes sense to pick either min or max value at any point from B.

You can try below solution with both of the above optimization.

possible_sum[][] = new Integer[n][2] // An array which memorize maximum possible sum till any n
initially possible_sum to some default value '-1'

int find_possible_sum(int i, int next, int minORmax){
    if(possible_sum[i][minORmax] != -1)return possible_sum[i][minORmax];
    possible_sum[i][minORmax] =  max(find_possible_sum(i-1, max_till_i, 0) + abs(max_till_i - next), find_possible_sum(i-1, minTill_i, 1)) + abs(min_till_i - next)); 
   // max_till_i and min_till_i can obtained in O(n) during pre-calculation
   return possible_sum[i][minORmax];
}




int max_value = -1 , min_value = MAX_VALUE;
   int min_till_i[], max_till_i[]; 
   for(int i=1;i<=n;i++){
        min_till_i[i] = min(B[i],min_value);
        min_value = min(min_value, B[i]);

        max_till_i[i] = max(B[i],max_value);
        max_value = min(max_value, B[i]);
    }

Total complexility of this solution should be around: \$O(n)\$ + \$O(2*n)\$