educative.io

Educative

Topic Correction - I believe this must be LIS instead of LDS!

Hi,

In the bottom up approach, We are doing a comparison for array[i]>array[j]. Shouldn’t we take the LIS and LIS reverse instead of LDS and LDS reverse since LDS will be the comparison of array[i]<array[j] or am I missing something. Please let me know.

Thanks,
Gautham

1 Like

Dear Gautham,

Thanks for reaching out. We’re glad to hear from you.
Your query has been logged, we’ll get back to you shortly.

Thanks & Regards!
Team Educative

@Gautham_Honnavara: Yes, even i had a similar understanding (that it is a Longest Increasing Sequence). You are correct.

We will wait for the official reply though :slight_smile:

Also to add my above reply, It is LIS only for the Bottom Up Approach and not others (like @Gautham_Honnavara mentioned)

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.

// find LDS from beginning-to-end of the array
// find LDS from end-to-beginning of the array

is this nums[j] < nums[i] LIS? I thought nums[j] > nums[i] should be LRS. Did I missed anything?

Hi @Franklin,

These are Longest Decreasing Subsequences (LDS) for every index to the beginning and the end of the array. More appropriate comments would be:

// find LDS for every index up to the beginning of the array
// find LDS for every index up to the end of the array

Hope this helps.

The above leetcode questions sounds similar. What I did is A.length - LBS(A), where A is the input array and LBS is the longest bitonic subsequence solution given by grokking. However the above problem is failing on this input(and few others also).

Input

[9,8,1,7,6,5,4,3,2,1]

Output

1

Expected

2