Suppose that we change the maximum subarray problem from the book as follows: in

Question

Suppose that we change the maximum subarray problem from the book as follows: instead of maximum subarray, we ask for the largest sized subarray that adds up to the smallest value and we change the input assumption to only non-negative integers. Does this simplify the problem enough so that we can give a much simpler algorithm for this problem than the one given in the book? If not, justify your answer carefully. If yes, then give simplest possible algorithm and analyze its complexity specifying the dominant term exactly instead of asymptotically.

Please explain in details and with example and please cover all the questions.

Explanation / Answer

Observations:

1. Only non-negative integers are allowed.

2. We want to find the largest sized subarray that adds up to the smallest sum.

We can naturally assume that we intend to minimize the ratio subset sum/ subset size for all possible subsets (may be non-contiguous) of the given array.

Algorithm

Input: Array a of size n.

Output: Indices of the beginning and end of the (possibly non-contiguous) subarray that minimizes subset sum/ subset size ratio.

Running time : There are 5 assignment operations in the beginning. The for loop runs (n-1) times. In each iteration there are at max 3 if else checks. At max 8 assignment operations in each iteration.

So it will take 5 + 8*(n-1) time at max.

For example take a = {2, 3, 4, 1, 2}

Output will be {1} with beginning = 3, end =3.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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