Author: Stan Eisenstat
Subject: Re: [Cs223] Practice Midterm Answers
Date: Tuesday, 03 Mar 2020, 20:26:12

    > Message Posted By: Unknown
    ...
    > I'm wondering if this is a typo on the practice midterm solutions for the
    > dynamic programming approach to finding largest subarray product:
    >
    > "Let P1(K) = largest product in X[0],...,X[K-1].
    >   Let P2(K) = largest product of the form X[I]*...*X[K-1], 0 <= I < K.
    >   Set P1(1) = X[0] and P2(1) = X[1].
    >   Set P2(K+1) = max (P1(K)*X[K], X[K]) and P1(K+1) = max {P1(K), P2(K+1)
    >     for 1 <= K < N"
    >
    > Shouldn't P2(k+1) be set to max (P2(K)*X[K], X[K]) since P1(K)*X[K] might
    > not be contiguous?

Good catch.  Thanks.

There was also an error in the explanation.  The answer
 should have been:

   Let P1(K) = largest product in X[0],...,X[K-1].
   Let P2(K) = largest product of the form X[I]*...*X[K-1], 0 <= I < K.
   Set P1(1) = X[0] and P2(1) = X[0].
   Set P2(K+1) = max (P2(K)*X[K], X[K]) and P1(K+1) = max {P1(K), P2(K+1)}
     for 1 <= K < N
    
   Explanation:
     P2(K+1) either includes X[K-1]*X[K] (= P2(K)*X[K]) or excludes X[K-1] and
       includes X[K] (= X[K]).
     P1(K+1) either excludes X[K] (= P1(K)) or includes it (= P2(K+1)).
    
I updated the web page to reflect this change.

--Stan-