Dynamic Programming #1: Longest Increasing Subsequence

This is the first video of Practical Programming Algorithm playlist.

[thecheekychinaman]

This is the first clear and comprehensible explanation of the problem Ive bumped into. Loving how you first show the desired outputs straight off - that really clears things up

[BoQianTheProgrammer]

You are right. Removing +1 makes the code more efficient. Good catch.

[jamesqiu]

This DP design idea is "limit the original sequence length-budget" and reuse them, which is presented nicely in the video, however I don't see the code/ explanation handle below situations:

[andrewdeighton]

in the inner loop over j, where it has D[j] < D[i] - that isn't comparing the 'tail' of any previously found sequence, it is comparing the the j'th entry in the input vector with the ith entry in the input vector, and that ignores what comes between j and i - I had to change that in a C# implementation - I'm sure it's a bug in the code - unless I mis-understood vectors.

[AmbujManiTripathi]

Thanks Bo!! You demonstrated it in much a simpler way.

[CalebGosiak]

Great explanation! Thank you for taking the time to post this!

[vivekpal]

Hi, thanks for this video. I like all your videos because you explain all the concepts in a very clear and concise way without unnecessary clutter. Could you please add more videos in your "Practical Programming Algorithms" playlist? May be extend to include common DP interview questions as well. Thanks, again.

[federicomengozzi]

Instead of using a second for loop that brings the complexity to O(N^2) it could just be used std::lower_bound to determine the position in which the new element should be placed in O(log N) to obtain an O(N log N) solution

[xplocal]

Thanks Bo for the nicely explained video.
But do we need the LIS to be a vector of vectors? For the code below, I am using two vector<int> arrays - one to store largest sequence length at each item and the other to store the index to the previous item

void
{
cout << "Enter integers separated by space, CTRL-Z to finish" << endl;
vector<int> vec(istream_iterator<int>(cin), {});

vector<int> lis(vec.size());
vector<int> lischain(vec.size());
fill(lis.begin(), lis.end(), 1);
fill(lischain.begin(), lischain.end(), -1);

int maxLen = 0, maxIdx = -1;
for (int i = 1; i < vec.size(); i++)
{
for (int j = 0; j < i; j++)
{
if (vec[i] > vec[j] && lis[j] == lis[i])
{
lis[i]++;
lischain[i] = j;
if (lis[i] > maxLen)
{
maxLen = lis[i];
maxIdx = i;
}
}
}
}
cout << "Longest inreasing subsequence length: " << maxLen << endl;
cout << "Longest increasing subsequence:" << endl;
deque<int> seq;
while (maxIdx >= 0)
{
seq.push_front(vec[maxIdx]);
maxIdx = lischain[maxIdx];
}
for (auto item : seq)
cout << item << ", ";
cout << endl;
}

[KartheekAchanta]

How can {3, 4, 5} can be forgotten ?, it gives the longest subsequence in the array, if it is not the reason, can you let me know why {3, 4, 5} is not included please?

[keithlevan]

The correct value of L[2] is 2, 6.  If the "+ 1" inside the inner for loop logic is removed, the algorithm will compute L[2] = 3, 6.  Why does Bo agree with Kevin to simplify this logic for "efficiency?"

[nirajabcd]

Took me a while to understand but nice explanation. Just wondering is there a way we could list out all possible increasing sub-sequences? Like {3, 4, 5} is missed out from the example input.

[jimcollins]

"and one even though it only has one element we can still consider it as an increasing sequence". Please explain.

[wiscatbijles]

Thanks, this helped me to solve my problem.

[FredoCorleone]

If you want to return the first longest subsequence:
function {
var best = []

var dp = nums.map(n => [n])

for (var i = 1; i < nums.length; i++) {
for (var j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j].length + 1 > dp[i].length) {
best = dp[i] = dp[j].concat(nums[i])
}
}
}

return best
}


That's JavaScript...

[tincustefanlucian]

Why {3, 4, 5} is not detected as the Longest Increasing Subsequence? It has the same length as {2, 4, 5} and it's the first one I have found.

[georgekjolly]

For an input Array {7, 9, 1, 2, 4, 10, 11}.
As per your method, I am getting the answer 7, 9, 10, 11. The correct answer is 1, 2, 4, 10, 11.
Please correct me if I am wrong.

[Vivek--blr]

{3, 4, 5} can also be an increasing sub sequence right ?

[konstantinrebrov]

That is a permutations and combinations formula!

[RahulSingh-exsm]

i had written same code its not working