Maximize value of (arr[i] – i) – (arr[j] – j) in an array in C++

Problem statement

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 the size of input array arr[].

If the input array is {7, 5, 10, 2, 3} then we can obtain 9 maximum value as follows−

(element 10 – index 2) - (element 2 – index 3) (10 – 2) – (2 – 3) = 8 – (-1) = 9

Algorithm

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

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int getMaxDiff(int *arr, int n){    if (n < 2) {       cout << "Invalid input" << endl;       exit(1);    }    int minVal = INT_MAX;    int maxVal = INT_MIN;    for (int i = 0; i < n; ++i) {       int result = arr[i] - i;       if (result > maxVal) {          cout << "Max = " << arr[i] << " - " << i << endl;          maxVal = result;       }       if (result < minVal) {          cout << "Min = " << arr[i] << " - " << i << endl;          minVal = result;       }    }    return (maxVal - minVal); } int main(){    int arr[] = {7, 5, 10, 2, 3};    int n = sizeof(arr) / sizeof(arr[0]);    cout << "Maximum value = " << getMaxDiff(arr, n) << endl;    return 0; }

Output

When you compile and execute the above program. It generates the following output −

Maximum value = Max = 7 - 0 Min = 7 - 0 Min = 5 - 1 Max = 10 - 2 Min = 2 - 3 9