Leetcode 152: Maximum subarray product - being interviewer, work with the peer over 32 minutes, gave major hint how to design dynamic programming solution

Leetcode 152: Maximum subarray product

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

 */


// products[0:idx] = arr[0] * ... * arr[idx]
time: O(N^2)
// (i, j) -> product[i] / product[j - 1]
space: O(N)
    
// dp[idx] -> max product from 0 to idx
// dp[0] = arr[0]
// dp[idx] = 
    
// -2 10 10 10
            dp[idx] = 1000
// -2 10 10 10 -2
        dp[idx + 1] = 4000
The peer did try to find transition from states to set up a dynamic programming solution,
and he said that he could not do it since minimum value is also involved.         
I asked him if he likes to give up, take a hint. And then he spent another 10 minutes to try, but 
he could not make it. He wrote down his analysis from line 26 to 33.
dp[idx + 1] = 2 [0:idx + 1]

dp[left_index][right_index]

2 1 400 1 23 4 9999 1 1 2000
    
numberOfNegativeNumbers[0:index] += 0 (arr[indedx] >= 0), 1 (arr[index] is negative)
(i, j) -> numberOfNegative(j + 1, N) is even -> (i, N) -> 
  
Julia gave out hint here from line 36 to line 52:    
// 0 -2 10 10 10 -2  -> subproblem should include min product 
             |
            max = 1000
            min = -2000
    
// minProduct[index] -> the min product that ends at position i
  
                max = min (previous) * -2 = 4000
                      1000 * (-2) = -2000

  subarray - start / end 
  brute force end position 
  for(i = 0; i < length; i++)
  {
    // end at positon at i - what is maximum product ending at position i
  }
---------------------------------------------

The peer took my hint quickly, he said that he likes to think about a few minutes, and then
he wrote down the following analysis from line 56 to line 62:

// minProduct[0] = maxProductn = arr[0]
// maxProduct[index] = max(arr[index],
                            maxProduct[index - 1] * arr[index],
                            minProduct[index - 1] * arr[index]);
// minProduct[index] = min(arr[index],
                            maxProduct[index - 1] * arr[index],
                            minProduct[index - 1] * arr[index]);

The peer wrote the code quickly. Here is the code:

long long getMaxProduct(const vector<int> &numbers)
{
    if (numbers.empty()) { return 0; }
    int len = (int)numbers.size();
    struct Result {
        long long minProduct, maxProduct;
    }
    vector<Result> resultsSoFar(n);
    
    // Base case
    resultsSoFar[0].minProduct = resultsSoFar[0].maxProdcut = arr[0];
    
    for (int idx = 1; idx < len; ++idx) {
        maxProduct[index] = max(arr[index],
                            maxProduct[index - 1] * arr[index],
                            minProduct[index - 1] * arr[index]);
minProduct[index] = min(arr[index],
                            maxProduct[index - 1] * arr[index],
                            minProduct[index - 1] * arr[index]);
    }    
}