Author: Stan Eisenstat
Subject: Re: [Cs223] Sample Midterm Example
Date: Tuesday, 03 Mar 2020, 07:44:52

    > Message Posted By: Unknown
    >
    > When the answers to the sample midterm are released, is there any way that
    > a small example can be included along with them, to show how the algorithm
    > works on a set of real values? (ex. showing the steps for one of the two
    > algorithms covered for practice problem one on an array of 5-7 numbers)

NOTE:  In the dynamic programming solution posted,
"P2(1) = X[1]" should be "P2(1) = X[0]".  I have
updated the web page to reflect this.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Suppose that the numbers are (7, .2, 5, 4, .3, 2).

Divide and conquer splits them into two groups
  (7, .2, 5) for which the largest product is L = 7
  (4, .3, 2) for which the largest product is R = 4
During the conquer stage,
  LP = max {5, .2*5, 7*.2*5} = 7
  RP = max (4, 4*.3, 4*.3*2} = 4
The value returned is max{L,R,LP*RP} = 28.

Dynamic programming computes:
  P2: X[0]=7, max{P1(1)*X[1],X[1]} = max{1.4,.2} = 1.4, 7, 28, 8.4, 16.8
  P1: X[0]=7, max{P1(1),P2(2)}     = max{7,1.4}  = 7,   7, 28, 28,  28
and returns P1(6) = 28.

--Stan-