HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Calculate $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ maximizes

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
mathbba_iwithgeqb_imaximizesthatcalculatesumand

Problem

I have two datasets $A$ and $B$:

$A = \{1, 5, -34, 34.34323, -23.5444, 9.43, ....\}$
$B = \{-0.5, 44, -0.243, -3455, 2.22221, -23.23, ....\}$

Those datasets contain a big amount of "random" numbers (They are actually not random, but their source does not matter for this question). Both datasets always have the same size.

Now I need to calculate two numbers $(u,v) \in \mathbb{R}$ so that $\sum (a_i + b_i)$ with $ a_i \geq u$ and $b_i \geq v$ reaches the biggest possible value.

For clarification: Say $a_3 \geq u$ but $b_3 < v$. Then $(a_3 + b_3)$ is not included in the sum. That is meant by $ a_i \geq u$ and $b_i \geq v$.

Does an algorithm for the solution to this problem already exist? If not, I am open for ideas.

Solution

For each pair of elements, $(a_{i},b_{i})$, you can calculate the sum of all the $(a_j+b_j)$ where $a_{j}$ and $b_{j}$ are both greater than or equal to $a_{i}$ and $b_{i}$. So an algorithm could look like:

largest_pair = 0
largest_value = -∞
for each i:
    for each j:
        total = 0
        if(a[j] >= a[i] & b[j] >= b[i])
            total += a[j] + b[j]
    if(total>largest_value)
        largest_value = total
        largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,v


This algorithm is $O(n^2)$ but is easily adaptable to n-variables, and there should be some shortcuts that could speed it up

Code Snippets

largest_pair = 0
largest_value = -∞
for each i:
    for each j:
        total = 0
        if(a[j] >= a[i] & b[j] >= b[i])
            total += a[j] + b[j]
    if(total>largest_value)
        largest_value = total
        largest_pair = i
u = a[largest_pair]
v = b[largest_pair]
output u,v

Context

StackExchange Computer Science Q#67820, answer score: 4

Revisions (0)

No revisions yet.