-----
__CLEAR CUTTER'S NEEDS YOUR HELP!__
-----

The logging company Clear Cutter's makes its money by optimizing the price-to-length of each log they cut before selling them. An example of one of their price tables is included:

```python
# So a price table p
p = [ 0,  1,  5,  8,  9, 10]

# Can be imagined as:
# length i | 0  1  2  3  4  5 *in feet*
# price pi | 0  1  5  8  9 10 *in money*
```

They hired an intern last summer to create a recursive function for them to easily calculate the most profitable price for a log of length _n_ using price table _p_ as follows:

```python
def cut_log(p, n):
   if (n == 0):
      return 0
   q = -1
   for i in range(1, n+1)
      q = max(q, p[i] + cut_log(p, n-i))
   return q
```

An example of the working code:
```python
cut_log(p, 5) # => 13
# 5ft = $10, BUT 2ft + 3ft = 5ft -> $5 + $8 = $13 which is greater in value
```

However, their senior software engineer realized that the number of recursive calls in the function gives it an awful running time of 2^n (as this function iterates through ALL 2^n-1 possibilities for a log of length n).

Having discovered this problem just as you've arrived for your internship, he responsibly delegates the issue to you.

Using the power of Stack Overflow and Google, he wants you to create a solution that runs in Θ(n^2) time so that it doesn't take 5 hours to calculate the optimal price for a log of size 50. (He also suggests to research the problem using the keywords in the tags)

__(Be aware that if your algorithm is not efficient, it will attempt to look at 2^49 = 562949953421312 nodes instead of 49^2 = 2401... The solution will automatically fail if it takes longer than 6 seconds... which occurs at right around Log 23)__

Difficulty: interview

Starter code:

def cut_log(p, n):
	

Solutions:
def cut_log(p, n):
    log = [0]
    for _ in range(n):
        log.append(max(pi + li for pi, li in zip(p[1:], log[::-1])))
    return log[n]


from functools import lru_cache

# Your new function as given to you by me, your boss.
@lru_cache(maxsize=None)
def cl(p, n):
   if (n == 0):
      return 0
   q = -1
   for i in range(1, n+1):
      q = max(q, p[i] + cut_log(p, n-i))
   return q

def cut_log(p, n):
    return cl(tuple(p), n)

from functools import lru_cache

# Not gonna reinvent the wheel
# Now I can go on codewars while they think I'm still working on it
# Be a smart intern
def cut_log(p, n):
    @lru_cache(maxsize=None)
    def rec(x):
        if not x: return 0
        return max(p[i] + rec(x-i) for i in range(1, x+1))
    return rec(n)

def cut_log(p, n):
    q = [0]
    for j in range(1, n+1):
        q.append(max(p[i] + q[j-i] for i in range(1, j+1)))
    return q[n]

def cut_log(p, n):
    best = p[:n+1]
    
    for j in range(2, n+1):
        best[j] = max(best[i] + best[j-i]  for i in range(j))
    
    return best[n]

def cut_log(p, n):
    # store the optimal prices of logs 
    plogs = [0]*len(p)
    for j in range(1, n+1):
        val = p[j]
        # second loop actually only has to iterate over a set half
        # the length of the current log since you're adding values
        # from either end.
        for i in range(1, j//2+1):
            # compare prices using optimal prices for lengths
            # smaller than your current length target, take max
            sm = plogs[i] + plogs[j-i]
            if sm > val:
                val = sm
        plogs[j] = val
    return plogs[n]

def cut_log(p, n):
  optim = [0]
  for j in range(1, n+1):
    q = -1
    for i in range(1, j+1):
      q = max(q, p[i] + optim[j - i])
    optim.append(q)
  return optim[n]


import array

def cut_log(p, n):
    r = array.array('i', [0]) * (n+1)
    for j in range(1, n+1):
        q = -1
        for i in range(1, j+1):
            q = max(q, p[i] + r[j - i])
        r[j] = q
    return r[n]


def cut_log(p, n):
    d = {}
    return cut_log_internal(p,n, d)
    
def cut_log_internal(p,n, d):
    if (n == 0):
      return 0
    elif n in d:
        return d[n]
    q = -1
    for i in range(1, n+1):
        q = max(q, p[i] + cut_log_internal(p, n-i, d))
    d[n] = q   
    return q

# Your new function as given to you by me, your boss.
def cut_log(p, n):
    values = [0 for _ in range(n + 1)]

    # Some array to store calculated values
    for j in range(1, n+1):
        values[j] = p[j]
        for i in range(1, j+1): # Two nested loops = Θ(n^2)
            v = values[i] + values[j - i]
            if v > values[j]:
                values[j] = v
            # Magic
    return values[n] # Good luck intern!