### Lyrics...

Pyramids are amazing! Both in architectural and mathematical sense. If you have a computer, you can mess with pyramids even if you are not in Egypt at the time. For example, let's consider the following problem. Imagine that you have a pyramid built of numbers, like this one here:

```
   /3/
  \7\ 4 
 2 \4\ 6 
8 5 \9\ 3
```

### Here comes the task...

Let's say that the *'slide down'* is the maximum sum of consecutive numbers from the top to the bottom of the pyramid. As you can see, the longest *'slide down'* is `3 + 7 + 4 + 9 = 23`

Your task is to write a function `longestSlideDown` (in ruby: `longest_slide_down`) that takes a pyramid representation as argument and returns its' __largest__ *'slide down'*. For example,

```python
longestSlideDown([[3], [7, 4], [2, 4, 6], [8, 5, 9, 3]]) => 23
```

### By the way...

My tests include some extraordinarily high pyramids so as you can guess, brute-force method is a bad idea unless you have a few centuries to waste. You must come up with something more clever than that.

(c) This task is a lyrical version of the __Problem 18__ and/or __Problem 67__ on [ProjectEuler](https://projecteuler.net).

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:
def longest_slide_down(pyramid):
	

Solutions:
def longest_slide_down(p):
	res = p.pop()
	while p:
		tmp = p.pop()
		res = [tmp[i] + max(res[i], res[i + 1]) for i in range(len(tmp))]
	return res.pop()


def longest_slide_down(pyr):
	for row in range(len(pyr) - 1, 0, -1):
		for col in range(0, row):
			pyr[row - 1][col] += max(pyr[row][col], pyr[row][col + 1])
	return pyr[0][0]


def longest_slide_down(pyramid):
	l = len(pyramid)
	for i in range(l - 2, -1, -1):
		for j in range(i + 1):
			pyramid[i][j] = max([pyramid[i + 1][j], pyramid[i + 1][j + 1]]) + pyramid[i][j]
	return pyramid[0][0]


class Tree(object):
	value = summ = None
	left = right = None

	def __init__(self, value):
		self.value = value

def iter_pairs(level):
	it = iter(level)
	(a, b) = (Tree(next(it)), Tree(next(it)))
	while b.value is not None:
		yield (a, b)
		(a, b) = (b, Tree(next(it, None)))

def build_tree(pyramid):
	it = iter(pyramid)
	root = Tree(next(iter(next(it))))
	prev_level = iter([root])
	for level in it:
		tree_level = []
		parent = next(prev_level)
		for (left_tree, right_tree) in iter_pairs(level):
			tree_level.append(left_tree)
			parent.left = left_tree
			parent.right = right_tree
			parent = next(prev_level, None)
		tree_level.append(right_tree)
		prev_level = iter(tree_level)
	return root

def calc_max_sums(root):
	if root is None:
		return 0
	if root.summ is not None:
		return root.summ
	root.summ = root.value + max(calc_max_sums(root.left), calc_max_sums(root.right))
	return root.summ

def find_max_slide(root):
	if root is None:
		return 0
	if not (root.left and root.right):
		return root.value
	if root.left.summ >= root.right.summ:
		return root.value + find_max_slide(root.left)
	if root.left.summ < root.right.summ:
		return root.value + find_max_slide(root.right)

def longest_slide_down(pyramid):
	tree = build_tree(pyramid)
	calc_max_sums(tree)
	return find_max_slide(tree)


def longest_slide_down(a):
	a = a[::-1]
	for j in range(1, len(a)):
		a[j] = [a[j][i] + max(a[j - 1][i], a[j - 1][i + 1]) for i in range(len(a[j]))]
	return a[-1][0]


def longest_slide_down(pyramid):
	if len(pyramid) == 1:
		return pyramid[0][0]
	(left, current) = (pyramid[:-1], pyramid[-1])
	pair_sum_g = map(max, zip(current[:-1], current[1:]))
	for (i, x) in enumerate(pair_sum_g):
		left[-1][i] += x
	return longest_slide_down(left)