title: How to obtain the trace of maximum triangle path sum?
body: <p>I am now struggling to solve this maximum triangle path sum problem.</p>
  
  <p>This problem is from <code>Euler project - 18</code>.</p>
  
  <pre><code>1
  8 1
  1 2 1
  1 5 3 1
  </code></pre>
  
  <p>I solve this case by the maximal sum and the path through which the sum is obtained.</p>
  
  <p>in this case, the answer is <code>1+8+2+5=16</code> and <code>c(-1,1,-1)</code>(↓ is -1 and ↘ is 1)</p>
  
  <p>I know the code by which the maximum sum is obtained.</p>
  
  <pre><code>chart[2, 1:2] &lt;- chart[2, 1:2] + chart[1, 1]
  for (i in 3:n) {
      chart[i, 1] &lt;- chart[i, 1] + chart[(i - 1), 1]
      chart[i, i] &lt;- chart[i, i] + chart[(i - 1), (i - 1)]
      for (j in 2:(i - 1)) {
          chart[i, j] &lt;- chart[i, j] + max(chart[(i - 1), (j - 1):j])`
          }
      }
  }
  result &lt;- max(chart[n, ])
  </code></pre>
  
  <p><a href="http://www.r-bloggers.com/project-euler-problem-18/" rel="nofollow">Here</a>  is a explanation page of this code</p>
  
  <p>But I do not know the code by which <code>the path</code> of the maximum sum is obtained.</p>