Practise for final

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]

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])

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]

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)