Tutorialspoint.dev

Maximize arr[j] – arr[i] + arr[l] – arr[k], such that i < j < k < l

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

Example:

Let us say our array is {4, 8, 9, 2, 20}
Then the maximum such value is 23 (9 - 4 + 20 - 2)



Brute Force Method:
We can simply find all the combinations of size 4 with given constraints. The maximum value will be the required answer. This method is very inefficient.

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[l] – arr[k] + arr[j] – arr[i], such that i < j < k < l

table1[] should store the maximum value of arr[l]
table2[] should store the maximum value of arr[l] – arr[k]
table3[] should store the maximum value of arr[l] – arr[k] + arr[j]
table4[] should store the maximum value of arr[l] – arr[k] + arr[j] – arr[i]



Then the maximum value would be present in index 0 of table4 which will be our required answer.

Below is the implementation of above idea –

C++

/* A C++ Program to find maximum value of
arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,
given that the array has atleast 4 elements */
#include <bits/stdc++.h>
using namespace std;
  
// To reprsent minus infinite
#define MIN -100000000
  
// A Dynamic Programing based function to find maximum
// value of arr[l] - arr[k] + arr[j] - arr[i] is maximum
// and i < j < k < l
int findMaxValue(int arr[], int n)
{
    // If the array has less than 4 elements
    if (n < 4)
    {
        printf("The array should have atlest 4 elements ");
        return MIN;
    }
  
    // We create 4 DP tables
    int table1[n + 1], table2[n], table3[n - 1], table4[n - 2];
  
    // Initialize all the tables to MIN
    for (int i=0; i<=n; i++)
        table1[i] = table2[i] = table3[i] = table4[i] =  MIN;
  
    // table1[] stores the maximum value of arr[l]
    for (int i = n - 1; i >= 0; i--)
        table1[i] = max(table1[i + 1], arr[i]);
  
    // table2[] stores the maximum value of arr[l] - arr[k]
    for (int i = n - 2; i >= 0; i--)
        table2[i] = max(table2[i + 1], table1[i + 1] - arr[i]);
  
    // table3[] stores the maximum value of arr[l] - arr[k]
    // + arr[j]
    for (int i = n - 3; i >= 0; i--)
        table3[i] = max(table3[i + 1], table2[i + 1] + arr[i]);
  
    // table4[] stores the maximum value of arr[l] - arr[k]
    // + arr[j] - arr[i]
    for (int i = n - 4; i >= 0; i--)
        table4[i] = max(table4[i + 1], table3[i + 1] - arr[i]);
  
    /*for (int i = 0; i < n + 1; i++)
        cout << table1[i] << " " ;
    cout << endl;
  
    for (int i = 0; i < n; i++)
        cout << table2[i] << " " ;
    cout << endl;
  
    for (int i = 0; i < n - 1; i++)
        cout << table3[i] << " " ;
    cout << endl;
  
    for (int i = 0; i < n - 2; i++)
        cout << table4[i] << " " ;
    cout << endl;
    */
  
    // maximum value would be present in table4[0]
    return table4[0];
}
  
// Driver Program to test above functions
int main()
{
    int arr[] = { 4, 8, 9, 2, 20 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    printf("%d ", findMaxValue(arr, n));
  
    return 0;
}

Python3

# A Python3 Program to find maximum value of
# arr[l] - arr[k] + arr[j] - arr[i] and i < j < k < l,
# given that the array has atleast 4 elements
  
# A Dynamic Programing based function to find
# maximum value of arr[l] - arr[k] + arr[j] - arr[i]
# is maximum and i < j < k < l
def findMaxValue(arr, n):
  
    # If the array has less than 4 elements
    if n < 4:
      
        print("The array should have atlest 4 elements")
        return MIN
  
    # We create 4 DP tables
    table1, table2 = [MIN] * (n + 1), [MIN] * n
    table3, table4 = [MIN] * (n - 1), [MIN] * (n - 2)
  
    # table1[] stores the maximum value of arr[l]
    for i in range(n - 1, -1, -1):
        table1[i] = max(table1[i + 1], arr[i])
  
    # table2[] stores the maximum
    # value of arr[l] - arr[k]
    for i in range(n - 2, -1, -1):
        table2[i] = max(table2[i + 1], 
                        table1[i + 1] - arr[i])
  
    # table3[] stores the maximum value of
    # arr[l] - arr[k] + arr[j]
    for i in range(n - 3, -1, -1):
        table3[i] = max(table3[i + 1], 
                        table2[i + 1] + arr[i])
  
    # table4[] stores the maximum value of
    # arr[l] - arr[k] + arr[j] - arr[i]
    for i in range(n - 4, -1, -1):
        table4[i] = max(table4[i + 1], 
                        table3[i + 1] - arr[i])
  
    # maximum value would be present in table4[0]
    return table4[0]
  
# Driver Code
if __name__ == "__main__":
  
    arr = [4, 8, 9, 2, 20]
    n = len(arr)
      
    # To reprsent minus infinite
    MIN = -100000000
  
    print(findMaxValue(arr, n))
  
# This code is contributed by Rituraj Jain

Output:

23

Time Complexity : O(n), where n is the size of input array
Auxiliary Space : Since we are creating four tables to store our values, space is 4*O(n) = O(4*n) = O(n)

Exercise for the readers:
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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter