Answer questions 1 and 2 by reading the text

Given a long string of letters y = y1y2 . . . yn, a segmentation of y is a partition of its letters into contiguous blocks of letters; each block corresponds to a word in the segmentation. The total quality of a segmentation is determined by adding up the qualities of each of its blocks. (So wed get the right answer above provided that quality(meet) + quality(at) + quality(eight) was greater than the total quality of any other segmentation of the string.)

Give an efficient algorithm that takes a string y and computes a segmentation of maximum total quality.

1) Problem Decomposition The recurrence for the maximum total quality OPT(n), together with a brief discussion about how it is obtained.

2) The Algorithm The pseudocode of the bottom-up implementation, including the details on how to construct the optimal segmentation. Your traceback procedure must have a time complexity O(n)