Home » Interview coding problems/challenges

Maximization of Quadruple

Maximization of Quadruple: You are given an array Arr, you have to find the maximum value of the expression (Arr[i1]-Arr[i2]+Arr[i3]-Arr[i4]), where i1>i2>i3>i4 and (0<=i1<=n-1,0<=i2<=n-2,0<=i3<=n-3,0<=i4<n-4).
Submitted by Divyansh Jaipuriyar, on August 22, 2020

Problem statement

You are given an array Arr, you have to find the maximum value of the expression (Arr[i1]-Arr[i2]+Arr[i3]-Arr[i4]) where i1>i2>i3>i4 and (0<=i1,i2,i3,i4<n).

Problem description

The problem basically asks you to find the quadruple of numbers whose combination as (Arr[i1]-Arr[i2]+Arr[i3]-Arr[i4]) is maximum for particular indexes (i1,i2,i3,i4) such that (i1>i2>i3>i4).

You should also keep in mind the index range as i1 can maximum be (n-1) similarly (i2<=n-2),(i3<=n-3) and (i4<=(n-4)).

Input

The first line of the input is the T number of test cases, each test case consists of N size of the input array, following line consist of N number of elements.

Output

You need to print the value of maximum of the given expression in a separate line for each test case.

Solution Approach

(a) Brute Force Approach:

In this approach, we will use the naive method of the nested loop. First, we will initialize ans variable with some minimum value then We will use for-loop each from 0 to its maximum index range.

As i1>i2>i3>i4 which implies i1<=n-1,i2<=n-2,i3<=n-3 and i4<=n-4 since we are using 0 based indexing.

Time complexity for the above approach in the worst case is: O(n^4)

Space complexity for the above approach in worst case i: O(1)

(b) Dynamic Programming Approach:

In this approach we will use extra space to beat time constraint as we are using exponential time in naive method.

Following steps will be used in our dynamic programming approach:

1. We will create four arrays/vector of size N+1, N, N-1, N-2 and our arrays will be f1[N+1],f2[N],f3[N-1] and f4[N-2].
2. After that, we will initialize all the elements of the given four arrays with INT_MIN value.
3. For the first array f1, we will iterate from index N-1 and fill its values based on the maximum value of the next element of f1 or current value from the array.
   

   for(i=n-1;i>=0;i--)
       f1[i]=max(f1[i+1],Arr[i])
   

4. For second array f2, we will fill it according to maximum value of:
   

   for(i=n-2;i>=0;i--)
   	f2[i]=max(f1[i+1]-Arr[i],f2[i+1]) 
       //so that our order of index i1>i2 is maintained 
       //and we get maximum value of Arr[i1]-Arr[i2].
   

5. For third array f3, we will fill it according to maximum value of:
   

   for(i=n-3;i>=0;i--)
       f3[i]=max(f3[i+1],f2[i+1]+Arr[i])
       //so that our order of index is maintained as 
       //i1>i2>i3 and also the equation Arr[i1]-Arr[i2]+Arr[i3] 
       //is maintained.
   

6. Finally for fourth array f4, we will fill it according to maximum value of:
7. Finally, the maximum value is stored in the array f4[0] position.

Time complexity for the above approach in the worst case is: O(n)

Space complexity for the above approach in the worst case is: O(1)

C++ Implementation (Brute Force Approach)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;
    
    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;
    
        ll arr[n];
    
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
    
        //initialize ans variable
        //with minimum value.
        ll ans = INT_MIN;

        //iterate through the array elements.
        //also follow the constraints of given
        //problem as i1>i2>i3>i4
        for (ll i = 0; i < n; i++) {
            for (ll j = 0; j < n - 1; j++) {
                for (ll k = 0; k < n - 2; k++) {
                    for (ll l = 0; l < n - 3; l++) {
                        if ((i > j) && (j > k) && (k > l))
                            ans = max(ans, arr[i] - arr[j] + arr[k] - arr[l]);
                    }
                }
            }
        }
        cout << "Maximum Quadruple is: ";
        cout << ans << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 6
Enter elements: 1 2 3 4 5 6
Maximum Quadruple is: 4
Enter size of array: 6
Enter elements: 3 9 10 1 30 40
Maximum Quadruple is: 46
Enter size of array: 8
Enter elements: 9 8 2 7 4 5 9 2
Maximum Quadruple is: 10

C++ Implementation (Dynamic Programming Approach)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        //define array.
        ll arr[n];

        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //initialize four arrays.
        ll f1[n + 1], f2[n], f3[n - 1], f4[n - 2];

        //fill all the elements
        //with minimum values.
        memset(f1, INT_MIN, sizeof(f1));
        memset(f2, INT_MIN, sizeof(f2));
        memset(f3, INT_MIN, sizeof(f3));
        memset(f4, INT_MIN, sizeof(f4));

        //now fill f1 with maximum values
        //of array arr.
        for (ll i = n - 1; i >= 0; i--)
            f1[i] = max(f1[i + 1], arr[i]);

        //now fill f2 with maximum values Arr[i1]-Arr[i2]
        //logic in mind.
        for (ll i = n - 2; i >= 0; i--)
            f2[i] = max(f2[i + 1], f1[i + 1] - arr[i]);

        //now fill f3 with maximum values Arr[i1]-Arr[i2]+Arr[i3]
        //logic in mind.
        for (ll i = n - 3; i >= 0; i--)
            f3[i] = max(f3[i + 1], f2[i + 1] + arr[i]);

        //now fill f4 with maximum value  of
        //Arr[i1]-Arr[i2]+Arr[i3]-Arr[i4] logic in mind.
        for (ll i = n - 4; i >= 0; i--)
            f4[i] = max(f4[i + 1], f3[i + 1] - arr[i]);

        cout << "Maximum Quadruple value: ";
        cout << f4[0] << "\n";
    }
 
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 6
Enter elements: 1 2 3 4 5 6
Maximum Quadruple value: 4
Enter size of array: 5 
Enter elements: 1 3 5 7 9
Maximum Quadruple value: 6
Enter size of array: 7
Enter elements: 6 3 8 9 2 3 5
Maximum Quadruple value: 9