I have two lists. List L1 contains all positive integers, list L2 contains positive numbers (e.g. 0.01,0.1,0.5,3,5,10,100....).
Given a small positive number M (e.g. 0.10948472), find a,b from L1 and cfrom L2 s.t. (b/a)*c is maximized but still <=M
Note that list L2 is fixed (length around 7000), list L1 has variable length (can have single element or up to 3000 elements).
How can we efficiently design an algorithm to solve this? I'm thinking about using divide and conquer on list L1 to break it into two then combine, but didn't work out. Anyone can solve it efficiently?
Update: Currently I worked out some inefficient but correct solutions: Sort 'L1' first. Divide 'L1' into two chunks: one chunk is the first N-1 elements, another chunk is the last element. Suppose best a,b,c has been found on the first N-1 elements of L1, I check whether we can find some a in first chunk and b in second chunk (one element only) and some c, such that (b/a)*c improves. Since I have to loop through each element in L2, although it's nlogn, still appears to be slow
Sort L1 ascending. Let's say |L1| = n. This is O(n log n).
For each element in L2 (the 'c' in the equation), do the following (so O(1) times since L2 is fixed).
1. For the first element in L1 (which we'll treat as the 'a' in the equation), use binary search on L1 to find a second element (the 'b') s.t. (b/a)*c is maximized but still <=M.
2. Now, we'll move on to the next element in L1. Note that we're increasing the denominator, so the numerator will either stay the same or increase. We'll just iterate rather than using binary search.
3. repeat step 2.
In steps 2 and 3 we keep track of the best values we've found so far for a, b, and c.
Running time: O(n log n) to sort, then in step 2 we only ever increment the numerator or denominator once from each value, so this is O(n) + O(n) = O(n).
This takes advantage of L2 being fixed. If |L2|=m and m isn't fixed then this would take O(n log n) + O(m*n)