1
$\begingroup$

All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...":

And, while this is a working assumption (the one that helps us solve the problem), I'm more curious on why one shall assume that and pick this approach? Or, in other words, how does one's thought process evolve and end up with an idea that an array must be introduced where each element is a length of a subsequence that ends at i -- here, I'm questioning exactly, why L[i] shall reflect a subsequence ending at i (i.e. why not starting at i)?

To better illustrate my question: when I was trying to solve the problem myself, without knowing the solution available on the Internet, I came to similar realizations: the first one is that a) I need an array L and the second one that b) L[i] will determine the length of a subsequence starting at i (!). I then proceeded with implementing the solution which turned out to be working (see below). The solution is equivalent to the most popular one, though this core assumption is directly opposite. When I read the popular solution, I began wondering, why didn't I think of this (i.e. L[i] -- length of a subsequence ending at i)? The answer might be just random -- i.e. "why not?", but maybe there's something else to it?

While backtracking my own thought process, I realized it was just a straightforward way to think for me when I was looking at an example sequence and tried to "mentally" solve the problem -- i.e. build subsequences as I go from 0 to N. Does it just mean that for someone (or the majority) the straightforward way was to think of how (or where) the subsequence ends?

    int lengthOfLIS(vector<int>& sequence) {
        if (sequence.size() == 1) return 1;
        if (sequence.size() == 0) return 0;

        int maxLen = 1;
        vector<int> LIS(sequence.size(), 1); // LIS[i] -- len of subseq starting at i
    
        for (int i = sequence.size()-2; i >= 0; --i)
            for (int j = i+1; j < sequence.size(); ++j)
                if (sequence[i] < sequence[j])
                {
                    LIS[i] = max(1+LIS[j], LIS[i]);
                    if (LIS[i] > maxLen) maxLen = LIS[i];
                }
    
        return maxLen;
    }
Improve this question
$\endgroup$
1
  • $\begingroup$ I'm not so clear on what you're asking. It is indeed possible to use the sequence starting at i, you're doing the same thing as the other approaches if you would first reverse the sequence. Choosing one or the other is just a case of presentation, and probably has no further implications beyond personal preference. If you want to delve deeper in this choice of presentation, please specify what you'd like to know about that. Also sometimes, a certain approach just "works out in the end", and has little justification a priori. $\endgroup$
    – Discrete lizard ♦
    Aug 24, 2021 at 6:41

1 Answer 1

Reset to default
1
$\begingroup$

Congratulation for solving a popular problem independently with a perspective that is rarely seen.

The choice between "ending at $i$" and "starting at $i$" can be dismissed as insignificant, coincidental, and random. They are symmetric to each other.

A similar question could be why we read, write and think from left to right, as shown on this web page and, much more often than not, in computer science and programming. Note, however, (most?) Arabians write from right to left.

On the other hand, there are, indeed, a few reasons why "ending at $i$" is seen overwhelmingly more often.

  • Assume we read and write from left to right.
    It is more natural to consider the sequences that start at the left side first, to be extended to the right. So, we would classify them according to where they end.

  • A convention across most (if not all) popular programming languages is that a dynamic array grows at the side where the index is larger.
    To be consistent with that direction, we would like to classify the subsequences according to their ending indices. In the case when we grow the given array (sequence), the code we have written and the computed (intermediate) result can be reused easier.

  • In general, it is more natural and common to extend subsequences (or anything) at their closing ends. "Extending the start of something" is more likely to sound weird. For example, a university can decide to extend a semester if it is about to end or even if it has ended, at which time the start of the semester cannot be extended earlier.
    Programming is hard. So people make every little effort to make it human-friendly. Or friendly to more people.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for sharing your thoughts on this! Let me add on why I thought this case was interesting to me. The LIS is a trivial problem. The fact that most solution platforms provide just one type of solution, reminds me of inherent algorithmic bias -- the same one that proves harmful in more complex cases such as AI (and which is usually introduced without anyone noticing, in their attempts to make the algorithm human-friendly). IMO, it's important to try to go "out-of-the-box", see working solutions that don't come naturally and compare, especially in a setting when one learns how to program. $\endgroup$
    – peetonn
    Aug 25, 2021 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.