Getting output of dynamic programming, (contiguous sub array, box stacking)

I am attempting to output the largest stack of boxes given an input of a set of boxes. Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this is the array being operated and changed, I then have another array that also has the values of the boxes going from largest to smallest.

 for(int i = 1; i < array.length; i++) {
for(int k = 0; k < i; k++) {
if(array[i].canStackOn(array[k])
&& maxWeight[i] < maxWeight[k] + temp[i].weight()) {
maxWeight[i] = maxWeight[k] + array[i].weight();
}
}

}


I am absolutely beating my brains out trying to find a way to keep track of each of the items added to the location of the largest sum on the array. Could anyone be so kind as giving pointers to a solution?

• Please replace your C/C++/Java code with pseudocode. – Yuval Filmus Oct 2 '17 at 12:05
• What's temp[i]? – D.W. Oct 2 '17 at 13:57

You are computing inductively an array maxWeight. The value of maxWeight at a certain point $i$ is the maximum over several possibilities. Currently you are remembering only the maximum itself. If you also store which possibility was maximum, then you will be able to use this additional information in order to construct an optimal solution.