### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Testers:** Misha Chorniy

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

simple

### PREREQUISITES:

basic implementation, arrays

### PROBLEM:

Given two arrays X and Y of length N. Find out the maximum value returned by this program.

```
input: integer N, list X[1, 2, ..., N], list Y[1, 2, ..., N]
output: integer res
function:
set res = 0;
for i := 1 to N do
for j := 1 to N do
for k := 1 to N do
if (X[i] = X[j]) OR (X[j] = X[k]) OR (X[k] = X[i])
continue
else
set res = max(res, Y[i] + Y[j] + Y[k])
return res
```

### SOLUTION

Note that we want to find the maximum value of Y[i] + Y[j] + Y[k] such that none of X[i], X[j] and X[k] are same.

We split the values array (X, Y) into groups of equal X values. This can be done by using a map data structure (map in C++). You can also do it using sorting.

For each of such group, we maintain the maximum Y value.

Now, we want to select three of the Y values from these groups.

Finally, if the number of such groups is at least 3, then we can pick the top 3 maximum of these Y values and output their sum.

Time complexity of this solution is \mathcal{O}(n \log n).