title: How to efficiently find out the maximum value below a threshold?
body: <p>I have two lists. List <code>L1</code> contains all positive integers, list <code>L2</code> contains positive numbers <code>(e.g. 0.01,0.1,0.5,3,5,10,100....)</code>.</p>
  
  <p>Given a small positive number <code>M</code> <code>(e.g. 0.10948472)</code>, find <code>a,b</code> from L1 and <code>c</code>from <code>L2</code> s.t. <code>(b/a)*c</code> is maximized but still <code>&lt;=M</code></p>
  
  <p>Note that list <code>L2</code> is fixed (length around <code>7000</code>), list <code>L1</code> has variable length (can have single element or up to <code>3000</code> elements).</p>
  
  <p>How can we efficiently design an algorithm to solve this? I'm thinking about using divide and conquer on list <code>L1</code> to break it into two then combine, but didn't work out. Anyone can solve it efficiently?</p>
  
  <p>Update: Currently I worked out some inefficient but correct solutions: Sort 'L1' first. Divide 'L1' into two chunks: one chunk is the first <code>N-1</code> elements, another chunk is the last element. Suppose best <code>a,b,c</code> has been found on the first <code>N-1</code> elements of <code>L1</code>, I check whether we can find some <code>a</code> in first chunk and <code>b</code> in second chunk (one element only) and some <code>c</code>, such that <code>(b/a)*c</code> improves. Since I have to loop through each element in <code>L2</code>, although it's nlogn, still appears to be slow</p>