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 (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? a) 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?

Explanation / Answer

In the array of the earnings, we have to find the largest sum contiguous subarray. The starting and end date would be the starting and ending position of the sunarray. We use the Kadane's algorithm for this.

Simple idea of the algorithm is to find all positive contiguous portions of the array (max_ending_here is used for this) and keep track of contiguous portion having max sum among all positive portions (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

The code is as follows:

#include<iostream>

#include<climits>

using namespace std;

void maxSubArraySum(int a[], int size)

{

int max_so_far = INT_MIN, max_ending_here = 0,

start =0, end = 0, s=0;

for (int i=0; i< size; i++ )

{

max_ending_here += a[i];

if (max_so_far < max_ending_here)

{

max_so_far = max_ending_here;

start = s;

end = i;

}

if (max_ending_here < 0)

{

max_ending_here = 0;

s = i + 1;

}

}

cout << "Maximum earning sum is "

<< max_so_far << endl;

cout << "Starting date "<< start+1

<< endl << "Ending date "<< end+1 << endl;

}

/*Driver program to test maxSubArraySum*/

int main()

{

int a[] = {-3,6,-4,10,-5,4,-3};

int n = sizeof(a)/sizeof(a[0]);

maxSubArraySum(a, n);

return 0;

}

a. Maximum earning sum is 12
Starting date 2
Ending date 4

b. For total n days, if starting day is 1 the ending day can be anything between 1 and n i.e. n choices. If starting date is 2, ending date can be anything between 2 and n i.e. n-1 choices. Similarly for starting 3, n-2 choices and so on. Thus total number of choices = n + n-1 + n-2 + n-3 + ... + n-(n-1) = n2 - (1+2+3+...+n-1) = n2 - n(n-1)/2 = (2n2 - n2 + n )/2                                                 = (n2 + n) / 2                                                     = n(n+1)/2

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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