let r[0..n] be a new array
 r[0] = 0
 for j = 1 to n
    q = -1
    for i = 1 to j
        for k = 0 to n-1
          q = Math.max(q[n][k], p[i] + q[n-i-1][k-1]);
    r[j] = q
 return r[n]