No caso em que queremos maximizar a soma do produto do número de elementos, o código abaixo representa uma implementação simples usando python que gera todas divisões possíveis que permitem a maximização. Como pode-se verificar escolhendo arbitrariamente um n, quaisquer divisões geram a mesma soma.
def maxSumProd(n,results={}): # n é o número de elementos da pilha original
if n==1:
return 0
if n==2:
return 1
else:
maxSum=0
for i in range(1,int(n/2)+1):
if n-i not in results:
results[n-i]=maxSumProd(n-i)
if i not in results:
results[i]=maxSumProd(i)
if (n-i)*i+results[n-i]+results[i]>=maxSum:
maxSum=(n-i)*i+results[n-i]+results[i]
print 'n','=',n,':',i,n-i
return maxSum
if __name__ == '__main__':
n=6
maxSumProd(n)
De forma análoga, geramos as divisões para a maximização da soma da soma dos elementos com o código abaixo. Nesse caso, a maximização é feita dividindo-se a pilha sempre em duas pilhas com 1 e n-1 elementos em cada.
def maxSumSum(n,results={}): # n é o número de elementos da pilha original
if n==1:
return 0
if n==2:
return 2
else:
maxSum=0
for i in range(1,int(n/2)+1):
if n-i not in results:
results[n-i]=maxSumSum(n-i)
if i not in results:
results[i]=maxSumSum(i)
if (n-i)+i+results[n-i]+results[i]>=maxSum:
maxSum=(n-i)+i+results[n-i]+results[i]
print 'n','=',n,':',i,n-i
return maxSum
if __name__ == '__main__':
n=6
maxSumSum(n)