## Friday, September 16, 2016

### Maximize value of (arr[i] - i) - (arr[j] - j) in an array - GeeksforGeeks

Related: Maximize arr[j] - arr[i] + arr[l] - arr[k], such that i < j < k < l - GeeksforGeeks
Maximize value of (arr[i] - i) - (arr[j] - j) in an array - GeeksforGeeks
Given an array, arr[] find the maximum value of (arr[i] – i) – (arr[j] – j) where i is not equal to j. Where i and j vary from 0 to n-1 and n is size of input array arr[].

```Input : arr[] = {9, 15, 4, 12, 13}
Output : 12
We get the maximum value for i = 1 and j = 2
(15 - 1) - (4 - 2) = 12
```
One important observation is, value of (arr[i] – i) – (arr[j] – j) can never be negative. We can alway swap i and j to convert a negative value into positive. So the condition i not equal to j is bogus and doesn’t require explicit check.
1) Find maximum value of arr[i] – i in whole array.
2) Find minimum value of arr[i] – i in whole array.
3) Return difference of above two values.
`int` `findMaxDiff(``int` `arr[], ``int` `n)`
`{`
`    ``if` `(n < 2)`
`    ``{`
`        ``cout << ``"Invalid "``;`
`        ``return` `0;`
`    ``}`

`    ``// Find maximum of value of arr[i] - i for all`
`    ``// possible values of i. Let this value be max_val.`
`    ``// Find minimum of value of arr[i] - i for all`
`    ``// possible values of i. Let this value be min_val.`
`    ``// The difference max_val - min_v`
`    ``int` `min_val = INT_MAX, max_val = INT_MIN;`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``if` `((a[i]-i) > max_val)`
`            ``max_val = a[i] - i;`
`        ``if` `((a[i]-i) < min_val)`
`            ``min_val = a[i]-i;`
`    ``}`

`    ``return` `(max_val - min_val);`
`}`

`int` `findMaxDiff(``int` `arr[], ``int` `n)`
`{`
`    ``if` `(n < 2)`
`    ``{`
`        ``cout << ``"Invalid "``;`
`        ``return` `0;`
`    ``}`

`    ``// Use two nested loops to find the result`
`    ``int` `res = INT_MIN;`
`    ``for` `(``int` `i=0; i<n; i++)`
`       ``for` `(``int` `j=0; j<n; j++)`
`          ``if` `( res < (arr[i]-arr[j]-i+j) )`
`            ``res = (arr[i]-arr[j]-i+j);`

`    ``return` `res;`
`}`

Read full article from Maximize value of (arr[i] - i) - (arr[j] - j) in an array - GeeksforGeeks