Assignment 5: Maximum product

Due: 5:00pm, Friday, October 3. Value: 40 pts.

You will not write a program for this assignment. (Blows your mind, doesn't it?) Instead, you should write up a typed solution, using Open Office Writer or Microsoft Word. .

1. Suppose we want an approach for determining the subsegment of an array of nonzero integers for which, when all numbers in the subsegment are multiplied, the product is largest. Consider the following array as an example.

   −4, 5, −6, 2, −1, 3

   For this array, the best subsegment includes all but the final two numbers, for a product of 240.

   The following program fragment illustrates one possible solution.

   int n = nums.length;
   int max = nums[0];
   for(int i = 1; i != n; i++) {
       int p = nums[i];
       int sub = p;
       for(int j = i - 1; j != -1; j--) {
           p *= nums[j];
           if(p > sub) sub = p;
       }
       if(sub > max) max = sub;
   }
   

   In terms of n, give the tightest possible big-O bound for the time spent by the above fragment. Explain why your bound is correct.

2. Explain why your big-O bound is the tightest possible bound for the given fragment.

3. Give an invariant for the outer loop of the above program fragment, leading to the conclusion that max will have the largest possible product at the fragment's end. Explain why your invariant is correct.

4. Invent a new algorithm to solve the problem which takes O(n) time, and write a program fragment implementing this algorithm. (Ok, so there's a bit of programming….) MaxProduct.java contains code which you might use for testing.

5. Argue that your algorithm computes the correct answer. You do not need a formal invariant.

6. Explain why your algorithm takes O(n) time.