Hi,
Could you please help me understand this solution to the problem.
A circus is designing a tower routine consisting of people standing atop one anothers shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
EXAMPLE:
Input:
(ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom:
(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)
My question is, how can fillNextSeq generate new sequences, if it doesn’t consider startFrom.
============================
public class Question {
ArrayList items;
ArrayList lastFoundSeq;
ArrayList maxSeq;
/ Returns longer sequence
ArrayList seqWithMaxLength(ArrayList seq1, ArrayList seq2) {
return seq1.size() > seq2.size() ? seq1 : seq2;
}
// Fills next seq w decreased wts&returns index of 1st unfit item.
int fillNextSeq(int startFrom, ArrayList seq) {
int firstUnfitItem = startFrom;
if (startFrom < items.size()) {
for (int i = 0; i < items.size(); i++) {
HtWt item = items.get(i);
if (i == 0 || items.get(i-1).isBefore(item)) {
seq.add(item);
} else {
firstUnfitItem = i;
}
}
}
return firstUnfitItem;
}
// Find the maximum length sequence
void findMaxSeq() {
Collections.sort(items);
int currentUnfit = 0;
while (currentUnfit < items.size()) {
ArrayList nextSeq = new ArrayList();
int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
maxSeq = seqWithMaxLength(maxSeq, nextSeq);
if (nextUnfit == currentUnfit)
break;
else
currentUnfit = nextUnfit;
}
}
