# Practise for final

## 1Dynamic Programming¶

### 1.1Question 1¶

#### 1.1.1Solution¶

def max_contiguous(seq):
#sums[i][j] means the maximum sum of the sequence with length i starting at index j
sums = [[0]*len(seq)]
sums.append([x for x in seq])
#skipping 1 because subseq sum of length 1 is already defined - the elements themselves
for i in xrange(2,len(seq)+1):
sums.append([])
for j in xrange(len(seq)-i+1):
#let m(c,k) = max(seq[c:k])
#m(c,k) = max(m(c,k-1),m(0,k),m(1,k),m(2,k)....m(k-1,k)
#we just apply a change of coordinates from (start,end) to (length,start)
terms_to_max = []
terms_to_max.append(sum(seq[j:j+i]))
terms_to_max.append(sums[i-1][j])
for c in xrange(1,i):
terms_to_max.append(sums[c][j+i-c])
sums[i].append(max(terms_to_max))
max_sum = sums[len(sums)-1][0]
#backtrack to find the first subseq with the max sum
for i in xrange(len(sums)):
for j in xrange(len(sums[i])):
if sums[i][j]==max_sum:
return seq[j:j+i]


No clue

### 1.3Question 3¶

#### 1.3.1Solution¶

Given in class, but here it is:

def max_profit(restaurants,k):
"""
restaurants - a sort list of tuples, where each tuple refers to (distance, profit)
k - minimum distance between two restaurants
"""
profits = [0]*len(restaurants)
profits[0]={"profit":restaurants[0][1],"restaurants":[0]}
for i in xrange(1,len(profits)):
#the profit not including the current restaurant
prev_max = profits[i-1]["profit"]

#the profit including the current restaurant
new_end = 0
for j in xrange(len(restaurants)):
if restaurants[j][0]>restaurants[i][0]-k:
break

new_end = j
include = profits[new_end]['profit']+restaurants[i][1]
new_restaurants = list(profits[new_end]['restaurants'])
new_restaurants.append(i)
if prev_max > include:
profits[i] = {"profit":prev_max,"restaurants":profits[i-1]["restaurants"]}
else:
profits[i] = {"profit":include,"restaurants":new_restaurants}
return max([profit['profit'] for profit in profits])


### 1.4Question 4¶

#### 1.4.1Solution¶

(it's constant time since a letter by itself is a valid word lol)

This solution runs in n3 rather than n2. not really sure how to improve it

def construct(txt):
validity = {}
for i in txt:
validity[i]= [i] if dict(i) else []
for i in xrange(2,len(txt)+1):
for j in xrange(len(txt)-i+1):
cur_str = txt[j:j+i]
if dict(cur_str):#it's a word, we're done
validity[cur_str] = [cur_str]
else:
#it's not a word, we have to see if it's a combination of valid words
for c in xrange(1,len(cur_str)):
left = txt[j:j+c]
right = txt[j+c:i+j]
lwords = validity[left]
rwords = validity[right]
#it's a combination of valid words
if len(lwords)>0 and len(rwords)>0:
validity[cur_str]=lwords+rwords
break
else:
validity[cur_str] = []
return validity[txt]


### 1.5Question 5¶

#### 1.5.1Solution¶

def longest_palindrome(seq):
seq = ' '.join(seq.replace(" ",""))
longest = [0]*len(seq)
for i in xrange(len(seq)):
if seq[i]!=' ':
longest[i]=1
offset = 1
while i-offset>=0 and i+offset<len(seq) and seq[i+offset]==seq[i-offset]:
if seq[i+offset]!=' ':
longest[i]+=2
offset+=1
return max(longest)