# Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l

Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l. Find the maximum value of arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l

Example:

```Let us say our array is {4, 8, 9, 2, 20}
Then the maximum such value is 23 (9 - 4 + 20 - 2)
```

Brute Force Method:
We can simply find all the combinations of size 4 with given constraints. The maximum value will be the required answer. This method is very inefficient.

Efficient Method (Dynamic Programming):

We will use Dynamic Programming to solve this problem. For this we create four 1-Dimensional DP tables.

Let us say there are four DP tables as – table1[], table2[], table3[], table4[]

Then to find the maximum value of arr[l] – arr[k] + arr[j] – arr[i], such that i < j < k < l

table1[] should store the maximum value of arr[l]
table2[] should store the maximum value of arr[l] – arr[k]
table3[] should store the maximum value of arr[l] – arr[k] + arr[j]
table4[] should store the maximum value of arr[l] – arr[k] + arr[j] – arr[i]

Then the maximum value would be present in index 0 of table4 which will be our required answer.

Below is the implementation of above idea –

## C++

 `/* A C++ Program to find maximum value of ` `arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l, ` `given that the array has atleast 4 elements */` `#include ` `using` `namespace` `std; ` ` `  `// To reprsent minus infinite ` `#define MIN -100000000 ` ` `  `// A Dynamic Programing based function to find maximum ` `// value of arr[l] - arr[k] + arr[j] - arr[i] is maximum ` `// and i < j < k < l ` `int` `findMaxValue(``int` `arr[], ``int` `n) ` `{ ` `    ``// If the array has less than 4 elements ` `    ``if` `(n < 4) ` `    ``{ ` `        ``printf``(````"The array should have atlest 4 elements "````); ` `        ``return` `MIN; ` `    ``} ` ` `  `    ``// We create 4 DP tables ` `    ``int` `table1[n + 1], table2[n], table3[n - 1], table4[n - 2]; ` ` `  `    ``// Initialize all the tables to MIN ` `    ``for` `(``int` `i=0; i<=n; i++) ` `        ``table1[i] = table2[i] = table3[i] = table4[i] =  MIN; ` ` `  `    ``// table1[] stores the maximum value of arr[l] ` `    ``for` `(``int` `i = n - 1; i >= 0; i--) ` `        ``table1[i] = max(table1[i + 1], arr[i]); ` ` `  `    ``// table2[] stores the maximum value of arr[l] - arr[k] ` `    ``for` `(``int` `i = n - 2; i >= 0; i--) ` `        ``table2[i] = max(table2[i + 1], table1[i + 1] - arr[i]); ` ` `  `    ``// table3[] stores the maximum value of arr[l] - arr[k] ` `    ``// + arr[j] ` `    ``for` `(``int` `i = n - 3; i >= 0; i--) ` `        ``table3[i] = max(table3[i + 1], table2[i + 1] + arr[i]); ` ` `  `    ``// table4[] stores the maximum value of arr[l] - arr[k] ` `    ``// + arr[j] - arr[i] ` `    ``for` `(``int` `i = n - 4; i >= 0; i--) ` `        ``table4[i] = max(table4[i + 1], table3[i + 1] - arr[i]); ` ` `  `    ``/*for (int i = 0; i < n + 1; i++) ` `        ``cout << table1[i] << " " ; ` `    ``cout << endl; ` ` `  `    ``for (int i = 0; i < n; i++) ` `        ``cout << table2[i] << " " ; ` `    ``cout << endl; ` ` `  `    ``for (int i = 0; i < n - 1; i++) ` `        ``cout << table3[i] << " " ; ` `    ``cout << endl; ` ` `  `    ``for (int i = 0; i < n - 2; i++) ` `        ``cout << table4[i] << " " ; ` `    ``cout << endl; ` `    ``*/` ` `  `    ``// maximum value would be present in table4 ` `    ``return` `table4; ` `} ` ` `  `// Driver Program to test above functions ` `int` `main() ` `{ ` `    ``int` `arr[] = { 4, 8, 9, 2, 20 }; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr); ` ` `  `    ``printf``(````"%d "````, findMaxValue(arr, n)); ` ` `  `    ``return` `0; ` `} `

## Python3

 `# A Python3 Program to find maximum value of ` `# arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l, ` `# given that the array has atleast 4 elements ` ` `  `# A Dynamic Programing based function to find ` `# maximum value of arr[l] - arr[k] + arr[j] - arr[i] ` `# is maximum and i < j < k < l ` `def` `findMaxValue(arr, n): ` ` `  `    ``# If the array has less than 4 elements ` `    ``if` `n < ``4``: ` `     `  `        ``print``(``"The array should have atlest 4 elements"``) ` `        ``return` `MIN` ` `  `    ``# We create 4 DP tables ` `    ``table1, table2 ``=` `[``MIN``] ``*` `(n ``+` `1``), [``MIN``] ``*` `n ` `    ``table3, table4 ``=` `[``MIN``] ``*` `(n ``-` `1``), [``MIN``] ``*` `(n ``-` `2``) ` ` `  `    ``# table1[] stores the maximum value of arr[l] ` `    ``for` `i ``in` `range``(n ``-` `1``, ``-``1``, ``-``1``): ` `        ``table1[i] ``=` `max``(table1[i ``+` `1``], arr[i]) ` ` `  `    ``# table2[] stores the maximum ` `    ``# value of arr[l] - arr[k] ` `    ``for` `i ``in` `range``(n ``-` `2``, ``-``1``, ``-``1``): ` `        ``table2[i] ``=` `max``(table2[i ``+` `1``],  ` `                        ``table1[i ``+` `1``] ``-` `arr[i]) ` ` `  `    ``# table3[] stores the maximum value of ` `    ``# arr[l] - arr[k] + arr[j] ` `    ``for` `i ``in` `range``(n ``-` `3``, ``-``1``, ``-``1``): ` `        ``table3[i] ``=` `max``(table3[i ``+` `1``],  ` `                        ``table2[i ``+` `1``] ``+` `arr[i]) ` ` `  `    ``# table4[] stores the maximum value of ` `    ``# arr[l] - arr[k] + arr[j] - arr[i] ` `    ``for` `i ``in` `range``(n ``-` `4``, ``-``1``, ``-``1``): ` `        ``table4[i] ``=` `max``(table4[i ``+` `1``],  ` `                        ``table3[i ``+` `1``] ``-` `arr[i]) ` ` `  `    ``# maximum value would be present in table4 ` `    ``return` `table4[``0``] ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``: ` ` `  `    ``arr ``=` `[``4``, ``8``, ``9``, ``2``, ``20``] ` `    ``n ``=` `len``(arr) ` `     `  `    ``# To reprsent minus infinite ` `    ``MIN` `=` `-``100000000` ` `  `    ``print``(findMaxValue(arr, n)) ` ` `  `# This code is contributed by Rituraj Jain `

Output:

```23
```

Time Complexity : O(n), where n is the size of input array
Auxiliary Space : Since we are creating four tables to store our values, space is 4*O(n) = O(4*n) = O(n)

This problem is simple yet powerful. The problem can be generalized to any expression under the given conditions. Find the maximum value of arr[j] – 2*arr[i] + 3*arr[l] – 7*arr[k], such that i < j < k < l