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:

C++

Download   Run Code

Output:

46

Java

Download   Run Code

Output:

46

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
steve
Guest

This is awesome!!

Yb
Guest

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

class solution {
public:
int max_expression_val(vector <int> &a)
{
int max_val = INT_MIN;
for (int i = 1; i < a.size() - 2; i++) {
int left = max_pair_val(a, 0, i);
int right = max_pair_val(a, i, a.size() - 1);
max_val = max(max_val, left + right);
}

return max_val;
}
private:
int max_pair_val(vector <int> &a, int start, int end)
{
if (end - start < 1)
return INT_MIN;

int with_end = a[end] - min_val(a, start, end - 1);
int wo_end = max_pair_val(a, start, end - 1);

return max(with_end, wo_end);
}

int min_val(vector <int> &a, int start, int end)
{
if (end == start)
return a[end];
return min(a[end], min_val(a, start, end - 1));
}
};

int main(int argc, char **argv)
{
solution s;
vector <int> a = {3, 9, 10, 1, 30, 40};

cout << s.max_expression_val(a) << endl;
exit(EXIT_SUCCESS);
}

Aman
Guest