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