Algorithm
Design and Problem Solving

Project
7: Maximize your profit

Hand-out:
2.11., deadline: 22.11.

**Story: **So many competitions
on TV! High time you’d also made some money on it. Questions are for you quite
trivial and it’s time to take your gain prize. N assistant girls are delivered
to you, they are holding hands of their neighbours. Each has a tag with an integer number on her
dress. You can win this sum (if a positive number) or lose it (a negative
number), when you choose this girl. You
can choose any number of girls but you can divide their chained hands maximally
on 2 places, i.e., the sequence of gain prizes which you will choose must be
continuous but can be of any length. You will not get the girls, only the sums,
so other than financial criteria are not to be considered.

- Solve
this problem by a simple, clear and correct
*O(**n*algorithm for^{2})**3 points**. - Solve
this problem by a correct
*O(**n log n)*algorithm based on D&C for**5 points**. - Solve
this problem by a correct
*O(**n)*algorithm based on dynamic programming for**7 points**.