## Thursday, July 28, 2016

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

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

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[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l
• table1[] will store the maximum value of arr[j]
• table2[] will store the maximum value of arr[j] – arr[i]
• table3[] will store the maximum value of arr[j] – arr[i] + arr[l]
• table4[] will store the maximum value of arr[j] – arr[i] + arr[l] – arr[k]
• So we iterate through table4[] the to get the maximum value which will be our required answer.
`long` `long` `int` `findMaxValue(``long` `long` `int` `arr[], ``int` `n)`
`{`
`    ``// If the array has less than 4 elements`
`    ``if` `(n < 4)`
`    ``{`
`        ``printf``(``"The array should have atlest 4 elements\n"``);`
`        ``return` `MIN;`
`    ``}`

`    ``// We create 4 DP tables`
`    ``long` `long` `int` `table1[n+1], table2[n+1], table3[n+1],`
`         ``table4[n+1];`

`    ``// Initialsing all the tables to MIN`
`    ``for` `(``int` `i=0; i<=n; i++)`
`        ``table1[i] = table2[i] = table3[i] =`
`                                    ``table4[i] =  MIN;`

`    ``// Filling table1[]`
`    ``for` `(``int` `i=n-1; i>=0; i--)`
`        ``table1[i] = max(table1[i+1], arr[i]);`

`    ``// Filling table2[]`
`    ``for` `(``int` `i=n-1; i>=0; i--)`
`        ``table2[i] = max(table2[i+1],`
`                        ``table1[i+1] - arr[i]);`

`    ``// Filling table3[]`
`    ``for` `(``int` `i=n-1; i>=0; i--)`
`        ``table3[i] = max(table3[i+1],`
`                        ``table2[i+1] + arr[i]);`

`    ``// Filling table4[]`
`    ``for` `(``int` `i=n-1; i>=0; i--)`
`        ``table4[i] = max(table4[i+1],`
`                        ``table3[i+1] - arr[i]);`

`    ``// Find maximum value in table4[]`
`    ``long` `long` `int` `res = MIN;`
`    ``for` `(i=0; i<=n-1; i++)`
`        ``res = max(res, table4[i]);`

`    ``return` `(res);`
`}`

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
Read full article from Maximize arr[j] - arr[i] + arr[l] - arr[k], such that i < j < k < l - GeeksforGeeks