title: Dynamic programming: finding largest triangle
body: <p>I need to find the largest triangle of ones in a matrix of zeros and ones using dynamic programming. So if this is my matrix:</p>
  
  <pre><code> 1 0 0 1 1
   0 1 1 1 1
   0 1 1 1 0
   1 1 1 1 1
   1 1 0 0 1
  </code></pre>
  
  <p>Then there are two largest triangles with the right corner at [2,2] and [4,4]. I only have to look for the right isosceles triangles (which have the angles 90◦, 45◦, 45◦) and I also need to look at only one orientation, because all the others are symmetric. So basically I need a function which takes the matrix and returns a triangle, with triangle being an object. I don't need complete code pseudocode is fine too me. </p>
  
  <p>First I thought of just using the square algorithm here: <a href="https://stackoverflow.com/questions/1726632/dynamic-programming-largest-square-block">Dynamic programming - Largest square block</a>, and when you have found the largest square, then the largest triangle must be in there. But I can easy find counter examples where this doesn't work. After that I tried to look at the upper cell and counting this with dynamic programming, but I am not sure what to do next... So my count will look like this with the matrix from above:</p>
  
  <pre><code>1 0 0 1 1
  0 1 1 2 2
  0 2 2 3 0
  1 3 3 4 1
  2 4 0 0 2
  </code></pre>
  
  <p>I think have to use this in some way.</p>
  
  <p><strong>UPDATE</strong>:</p>
  
  <p>I think I am pretty close now, when you walkthrough the matrix n*m and and make count[i][j] = 1+ min(count[i-1][j], count[i][j-1]), so look at the left and upper cell. We get this:</p>
  
  <pre><code>1 0 0 1 1
  0 1 1 2 2
  0 1 2 3 0
  1 2 3 4 1
  1 2 0 0 1
  </code></pre>
  
  <p>This looks pretty good to me, you can the see where the right corner is of the [4,4] solution. Can anyone think of any counter examples? I only I have to return one solution, so returning this solution is fine.</p>
  
  <p><strong>UPDATE 2:</strong>
  I have found a counterexample, let position [4,4] be 0, we then get the following matrix:</p>
  
  <pre><code> 1 0 0 1 1
   0 1 1 1 1
   0 1 1 1 0
   1 1 1 0 1
   1 1 0 0 1
  </code></pre>
  
  <p>Count will look like this after walking through the matrix:</p>
  
  <pre><code>1 0 0 1 1
  0 1 1 2 2
  0 1 2 3 0
  1 2 3 0 1
  1 2 0 0 1
  </code></pre>
  
  <p>Now it will return the triangle with right corner [3,4] (third row fourth column), which is incorrect it should find [2,2]. So I thought maybe just going from the top left (what we have done so far) and from the right bottom and take the max from that. So count with right bottom will look like this (look at the cell below and to the right):</p>
  
  <pre><code>1 0 0 2 1
  0 4 3 2 1
  0 3 2 1 0
  2 2 1 1 1
  1 1 0 0 1
  </code></pre>
  
  <p>Now we do find the solution of [2,2]. So I think using these methods will give me the solution, can anyone think of a better solution or a counter example for this one?</p>
  
  <p><strong>UPDATE 3:</strong>
  kraskevich made me realize that we have to use this algorithm four times. From the top left, top right, bottom left, bottom right and then just take the maximum, because then you have taken all the possibilities. Anyone has a better way to do this? Is this algorithm then correct? (So just four times the same algorithm, only an other start point in the matrix)</p>
  
  <p>Also for the people who don't really understand what I am doing (I might go a little fast) take a look again at this: <a href="https://stackoverflow.com/questions/1726632/dynamic-programming-largest-square-block">Dynamic programming - Largest square block</a> the approach is very similar and it is very well explained there what there is done.</p>