MinMaxDivision.py

# you can use print for debugging purposes, e.g.
# print "this is a debug message"
import itertools

def calc_cell(sol, m, n, sums):
    sol[m][n] = min(itertools.imap(
        lambda i: max(sol[m - 1][i], calc_sum(sums, i, n)), xrange(m - 1, n)))

def calc_sum(sums, i, j):
    return sums[j] - sums[i]

def solution(K, M, A):
    n = len(A)

    if K >= n:
        return max(A)

    sums = [0] * (n + 1)

    for i, e in enumerate(A):
        sums[i + 1] = sums[i] + e

    if K == 1:
        return sums[n]

    # sol[K][n]
    sol = reduce(lambda a, b: a + [[None] * (n + 1)], xrange(K - 1), [None] +
        [[None] + map(lambda j: calc_sum(sums, 0, j), xrange(1, n + 1))])

    for i in xrange(2, K):
        for j in xrange(i, n - K + i + 1):
            calc_cell(sol, i, j, sums)

    calc_cell(sol, K, n, sums)
    return sol[K][n]

print solution(3, 0, [2, 1, 5, 1, 2, 2, 2])