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