Thanks Gautham and Mohan for pointing this out. The bottom-up approach is actually LIS, sorry for the confusion.
Having said that, since the brute-force and Memoized solutions are based on LDS, we’ve changed the bottom-up solution to have a similar approach too. In other words, we will iterate through all the numbers and find the LDS in both the directions. Here is the code that is changed, only the inner loop and the ‘if’ condition is reversed:
// find LDS from beginning-to-end of the array
for (int i = 0; i < nums.length; i++) {
lds[i] = 1; // every element is an LDS of length 1
for (int j = i - 1; j >= 0; j--)
if (nums[j] < nums[i]) {
lds[i] = Math.max(lds[i], lds[j] + 1);
}
}
// find LDS from end-to-beginning of the array
for (int i = nums.length - 1; i >= 0; i--) {
ldsReverse[i] = 1; // every element is an LDS of length 1
for (int j = i + 1; j < nums.length; j++)
if (nums[j] < nums[i]) {
ldsReverse[i] = Math.max(ldsReverse[i], ldsReverse[j] + 1);
}
}
Hope this helps.