3. (20 points) Dynamic Programming You own a waterpark and are deciding what day

Question

3. (20 points) Dynamic Programming You own a waterpark and are deciding what days to open for the summer. Some days the park does well and you make money and other days there are not enough visitors and you lose money. Based on data from previous years you have come up with a guess for the amount of money you will make every day from the earliest possible opening day until the last possible closing day for a total of n days. Some days are positive earnings and some are negative earnings. You want to pick and opening day and a closing day that maximizes your summer earnings. Here is a short sample input. P I-3,6,-4,10,-5,4,-3] a) (2 points)If we open on the first day and close on the last day then we will earn a total of 5. What opening day and closing day should we select instead so that we maximize the earnings over these days? b) (2 points) If we have n days how many different starting and ending days do we have assuming the start day must always be earlier or equal to the end day? c) (2 points) Consider a brute force algorithm that will calculate the earnings for every pair of start and end days. What is the worst case running time of this algorithm?

Explanation / Answer

Ans (b)-If we have n days ,we can calculate number of different starting and closing days by 2n-1

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.