Its been quite sometime since I did some coding. Last Sunday, one of the best friends of mine (Clement Lloyd) asked me if I can solve Project Euler's Problem 18. The problem name is Maximum path sum. Finally I got some time today and it is a simple Dynamic Programming Problem. The basic idea is to, keep on adding two adjacent elements of each row with the corresponding element in the previous row and keep the maximum of them. For example,

 8
1 2

The maximum of 8+1 and 8+2 would be 10 and 10 would take 8's place. So we keep on doing this till we reach the top. For the sample input

3
  7 4
 2 4 6
8 5 9 3

After first Iteration,

3
   7  4
 10 13 15

After second Iteration,

3
  20 19

After third Iteration,

23

Here is the solution which I used

import sys
sys.stdin  = open ("Input.txt")
sys.stdout = open ("Output.txt", "w")
Array = []
for line in sys.stdin: Array.append (map (int, line.split()))
Array.reverse()
temp_array = [0] * (len(Array) + 1)
for Row in Array:
 for i in xrange (len(Row)):
  temp_array[i] = Row[i] + max (temp_array[i], temp_array[i + 1])
print max (temp_array)

This solution will solve Project Euler's Problem 67 as well.