I am very lost in this introduction, and ask for help to get the logic.
Here, the professor introduces four ways:1.greedy 2. divide & conquer 3.linear time 4.reconstruction.
For 1.greedy, it may produce a not maxium result. So it's out.
For 2.divide & conquer, it takes exponential time, too slow. So it's out.
Here, it comes my confusion.
I can't figure out the difference between linear time and reconstruction. Why it costs O(n) and What's the fill-in array used for?
Are both of 3.linear time and 4.reconstruction Dynamical Programming?