title: Compose biggest-sum row solution from two dimensional array algorithm optimalization
body: <p>Suppose we have a two dimensional array (N rows, M columns), in which each column has at least one non-empty cell with integer value:</p>
  
  <p><a href="https://i.stack.imgur.com/59lLy.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/59lLy.png" alt="Data"></a></p>
  
  <p>We can easily compose a new single row, in which each cell contains the biggest value taken from according column in data array.</p>
  
  <p><strong>The solution (length M) cannot have empty values.</strong></p>
  
  <p>In this case, the solution would be:</p>
  
  <p><a href="https://i.stack.imgur.com/9uCuK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/9uCuK.png" alt="Solution"></a></p>
  
  <p>There is a single factor: biggest value for each column.</p>
  
  <p>We want to add another factor: lowest amount of rows from which the solution is being composed from (<strong>more important</strong> than sum value).</p>
  
  <p>The simplest algorithm for this would be as following:</p>
  
  <p>i = 1</p>
  
  <pre><code>while (i &lt;= M)
  {
      candidates = generateCorrectSolutionsFromAllNLengthRowCombinations(i)
  
      if ( ! empty(candidates))
      {
          return biggestSumElement(candidates)
      }
  
      i++
  }
  </code></pre>
  
  <p>This algorithm returns correct solution, but has very high computional complexity which is problematic for bigger matrices.</p>
  
  <p>Is there a way to do it faster? Was this problem (or similar one) analyzed anywhere? </p>
  
  <p>Regards,</p>
  
  <p>Patryk</p>