# Maximize the Value of an Expression

Given an array A, maximize value of the expression (A[s] – A[r] + A[q] – A[p]) where p, q, r and s are indices of the input array and s > r > q > p.

For example,

Input:  A[] = [3, 9, 10, 1, 30, 40]

Output: 46

(40 – 1 + 10 – 3) will result in maximum value

Naive solution would be to generate all combinations of such numbers. The time complexity of this solution would be O(n4).

We can use Dynamic Programming to solve this problem. The idea is to create four lookup tables L1[], L2[], L3[] and L4[] where –

• L1[] stores the maximum value of A[s]
• L2[] stores the maximum value of A[s] – A[r]
• L3[] stores the maximum value of A[s] – A[r] + A[q]
• L4[] stores the maximum value of A[s] – A[r] + A[q] – A[p]

Then the maximum value would be present in index 0 of L4[], which is our required answer.

Below is its C++/Java implementation:

Output:

46

## Java

Output:

46

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).     (2 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Kausik Sen

But how are you being sure that maximizing the sum in each sub-problem will ultimately give you the maximum sum as output? Whenever you are choosing a particular p,q or r, you are restricting the possible values that s can take. Hence, it may not lead you to the solution every time. This particular case was easy as the max s was the rightmost element and the min s was the leftmost element. I think that other combinations will not work every time with this algo. Guest

This is awesome!! Guest

awesome algorithm! Guest Guest