Subset optimization with composite aggregate functions

Question

I have a finite set $P = \{1, 5, 3, 6, 4, ..., p_n\}$ of size $N$ and average $A$.

I want to find the most efficient way to maximize the following function:

$$ f(x, y) = \frac{1}{(1+e^{-6(x-2)})(1+e^{-6(y-2)})(1+e^{-0.1x-0.3y+1.5})} $$

where:

• $S \subsetneq P$;
• $x = |S|$;
• $y = \frac{min(S)}{A}$.

I really have no idea where to start other than sorting $P$. I'm looking for optimal time complexity or at least something considerably better than bruteforcing.

The conflicting extreme ideas are:

1. Taking a subset with $|S| = 1$ where the only element is $s = max(P)$. This will maximize the $y$ part but minimize the $x$ part.

2. Taking a subset with $|S| = N-1$ where the element that's excluded is $s = min(P)$. This will maximize the $x$ part but minimize the $y$ part.

Answer 1

If the set is unsorted, a time complexity of $O(N\log(N)$) is the best we can do, as that is the time complexity of sorting a list.

Let $Q$ be $P$ after it is sorted. We can consider $N-1$ cases.

For each case $1 ≤ i ≤ N-1$, let $S$ be the subset consisting of the last $i$ elements of the sorted set $Q$. Then:

$x = |S| = i$

$y = min(S)/A = Q[N-i]/A$

$f(x, y)$ would be evaluated $N-1$ times, for a time complexity of $O(N)$.

Since the slowest part of this process is $O(N\log(N))$, that is the time complexity of the overall process. The longest part of this would be sorting the list; calculating the maximum would be faster for large values of $N$.

If the set was presorted, this solution would have a $O(N)$ time complexity.

This solution is the optimal solution because $f(x, y)$ increases as $x$ increases or $y$ increases. A proper subset $S$ with a minimum value $M$ that does not contain all the values of $Q$ greater than or equal to $M$ could have the calculated $x$ value increased by including those values greater than or equal to $M$. As there are $N-1$ possible minimum values to consider, a time complexity of $O(N)$ is the fastest possible for this part of the solution.