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:
- 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].
- After that, we will initialize all the elements of the given four arrays with INT_MIN value.
-
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])
-
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].
-
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.
- Finally for fourth array f4, we will fill it according to maximum value of:
- 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