Dynamisk programmering 3

Detta är materialet till föreläsning 11 som är direkt efter föreläsning 10 den 19 september 2016. Vi använder omvänd undervisning (flipped classroom) för detta moment i kursen, vilket innebär att du före föreläsningen ska titta på dessa videor och försöka svara på tillhörande småuppgifter. Om du undrar något efter att ha gått igenom materialet får du gärna använda kommenterafunktionen för att ställa frågor som kan besvaras på föreläsningen. I övrigt kommer föreläsningen att bestå av problemlösning gruppvis och gemensamt.

• Titta på första videon.
• Använd informationen i totmaxpos och maxpos[i] för att konstruera och returnera elementen i den längsta delföljden. (Det kan finnas flera lika långa längsta delföljder, men algoritmen har bara lagrat information om en av dom i totmaxpos och maxpos.)
  Skriv pseudokod för konstruktionen av lösningen och analysera sedan tidskomplexiteten för konstruktionen.
• Klicka här när du är klar för att jämföra din lösning med Viggos och se på nästa video.