CSCC73H3 Lecture Notes - Dynamic Programming, Substring, Subsequence
19 Oct 2011
School
Department
Course
Professor
Document Summary
Due: november 9, 2010, by 10:30 am (in the drop box for your cscc73 tutorial section, near room sw-626a) Appended to this document is a cover page for your assignment. Fill it out, staple your answers to it, and deposit the resulting document into the course drop box (without putting it in an envelope). Part (ii) is often immediate from the de nitions. S is a subsequence consisting of consecutive elements of s. for instance, if s is (exercise 6. 1 in dpv, slightly reworded. ) 5, 15, 30, 10, 5, 40, 10 then 15, 30, 10 is a contiguous subsequence of s, but 5, 15, 40 is not. Input: a list of numbers s = a1, a2, . Output: the maximum number m such that m is the sum of all elements of a contiguous subsequence of s. (we de ne the sum of an empty subsequence to be 0. )
