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.

 

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