Question

Recall that a contiguous subarray is all of the elements in an array between indices

i
and
j
, inclusive (and if
j we define it to be the empty array). Call a subarray is nearly contiguous if it is contiguous (i.e. contains all elements between indices
i
and
j
for some
i,j
) or if it contains all but one of the elements between
i
and
j
. For example, in the array
[0,1,2,3,4]
, -
[0,2,3]
is nearly contiguous (from 0 to 3 , skipping 1 ), sum is 5 -
[0,1,2,3]
is nearly contiguous (because it is contiguous from 0 to 3 ), sum is 6 . -
[2,4]
is nearly contiguous (from 2 to 4 , skipping 3 ), sum is 6 . - [3] is nearly contiguous (because it is contiguous from 3 to 3 ), sum is 3 . - [] is nearly contiguous (because it is contiguous from 1 to 0 ), sum is 0 . -
[0,2,4]
is not nearly contiguous (because you'd have to remove two elements). The sum of a nearly contiguous subarray is the sum of the included elements. Given int [] A, your task is to return the maximum sum of a nearly contiguous subarray. For example, on input
[10,9,−3,4,−100,−20,15,−5,9]
your algorithm should return 24 (corresponding to
i=
6,j=8
and skipping the
−5
). (a) Define one or more recurrences to solve this problem. (b) Give English descriptions (1-2 sentences each should suffice) for what your recurrences calculate. Be sure to mention what any parameter(s) mean. (c) How do you caclulate your final overall answer (e.g. what parameters input to which of your recurrences do you check). (d) What memoization structure(s) would you use? (e) What would the running time of your algorithm be (you do not have to write the code). Justify in 1-3 sentences.

Answer 1

(a) One possible recurrence to solve this problem is:

Let f(i, j) be the maximum sum of a nearly contiguous subarray ending at index j and starting at index i or before.

Then the recurrence can be written as:

f(i, j) = max(f(i, j-1), f(i, j-2) + A[j])

This recurrence calculates the maximum sum of a nearly contiguous subarray ending at index j and starting at index i or before by considering two possibilities:

The subarray does not include the element at index j. In this case, the maximum sum is the same as the maximum sum ending at index j-1.

The subarray includes the element at index j, but skips the element at index j-1. In this case, the maximum sum is the sum of the elements ending at index j-2 plus the element at index j.

(b) Another possible recurrence to solve this problem is:

Let g(i, j) be the maximum sum of a contiguous subarray ending at index j and starting at index i or before.

Then the recurrence can be written as:

g(i, j) = max(g(i, j-1) + A[j], A[j])

This recurrence calculates the maximum sum of a contiguous subarray ending at index j and starting at index i or before by considering two possibilities:

The maximum sum of the subarray includes the element at index j. In this case, the maximum sum is the sum of the maximum sum ending at index j-1 plus the element at index j.

The maximum sum of the subarray does not include the element at index j. In this case, the maximum sum is simply the element at index j.

(c) To calculate the final overall answer, we can input the values 0 and n-1 into both recurrences, where n is the length of the array A. This will give us the maximum sum of a nearly contiguous subarray that starts at the beginning of the array and ends at the end of the array.

(d) To implement these recurrences using memoization, we can use a two-dimensional array to store the calculated values of f and g. The array can be initialized with values of 0 for all indices, and then we can fill in the values starting from the bottom right corner and working our way towards the top left corner.

(e) The running time of this algorithm would be O(n^2), because we need to calculate the values of f and g for every possible pair of indices i and j. This requires O(n^2) time in the worst case.