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
Enter size of array: 6
Enter elements: 3 9 10 1 30 40
Enter size of array: 8
Enter elements: 9 8 2 7 4 5 9 2
```

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
Enter size of array: 5
Enter elements: 1 3 5 7 9
Enter size of array: 7
Enter elements: 6 3 8 9 2 3 5