Find the maximum possible summation of differences of consecutive elements

user_4384490 0
Viewed 112

Array A contains the elements, A1,A2...AN. And array B contains the elements, B1,B2...BN. There is a relationship between Ai and Bi, for 1 = i = N, i.e., any element Ai lies between 1 and Bi.

Let the cost S of an array A be defined as:

Cost of the array S

You have to print the largest possible value of S.
The Link to the problem is Problem

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 a 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 O(n*2^n)

dynamic-programming recursion data-structures arrays algorithm
1 Answers

First, there is no reason that a[i] should be equal to any number besides 1 and b[i]. Realizing that we can write down a simple recurrence:

fmax(1) = fone(1) = 0
fmax(i) = max(fone(i-1) + b[i] - 1, fmax(i-1) + abs(b[i]-b[i-1]))
fone(i) = max(fone(i-1), fmax(i-1) + b[i-1] - 1)

answer = max(fmax(N), fone(N))

Where fmax(i) is a maximal sum for a[1..i] elements that end with b[i], fone(i) is a maximal sum for a[1..i] elements that end with 1.

With dynamic programming approach, the complexity is O(N).

user_47592000
Related