May 2 10:00 PM mock interview one hours - being an interviewer

Leetcode 152 Maximum Product Subarray

#include <vector>
#include <limits>
#include <algorithm>
#include <iostream>
using namespace std;


/*
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

pramp.com


[2 3 6 -4]

[2, 3, -2] i = 0; j = 2, subarray product = 2 * 3 * (-2)

i = 0
j = 0, 1, 2  // find product [0,0], [0, 1], [0, 2]

i = 1
j = 1, 2     // find product [1, 1], [1, 2]

i = 2
j = 2        // find product [2, 2]


startIndex/ endIndex  <-  brute force
dp 
subarray ending at index i   <- find solution by getting max from all i options 
go through i = 0, 1, 2, ....
build recurrence formula 

 i = 0, base case -> ending at index = 0 -> maximum product will be arr[0]
 
  what is subarray ending at index i - maximum value
  [2, 3, -2],   index = 2, subarray ending at index = 2, what is maximum value? -2
   [2, 3, -2]  -12
     [3, -2]   -6 
        [-2]   -2 
        
  [2, 3, -2, -1]
            what is subproblem ending at index = 3, maximum product?
  
     [2,  3,  -2,  -1]
     
     endIndex = 0
max   2   
min   2   

     endIndex = 1
     [...],3
how do you get max and min
     [3] standalone subarray
     at least some numbers before 3
     max_i * 3
     min_i * 3
  
  
     curmax = 1  // most pos value so far (upto index)
     curmin = 1  // most neg value so far (upto index)
     
     realmax = ? // value at end of array, to be returned to caller.
  
  
      a[2,  3,  -2,  -1]
      
      
       5   -8
            ^     
      index = j;
      if (a[j] > 0)
        curmax = curmax(upto j-1) * a[j];
        curmin = min( curmin * a[j], 1)
      else (a[j] < 0)
        curmax = 
      else  // a[j] == 0
        curmax = 
        curmin = 
      


realmax = 2;
      
      index = 1;
      curmax = 6;
      curmin = 6;  //  ?
      realmax = 6;
         [3]  -> 3
         [2, 3]-> 6
         
      index = 2;
      curmax = max(maxPrevious * (-2), minPrevious * (-2), -2)
      curmin = min(maxPrevious * (-2), minPrevious * (-2), -2)
     
     [ -1, 2, 3, 4, -2]
     
     [ -1, 0, 2,3, 4, -2]
     2, 3, 0, 2, 3, 0, -2
       
*/

/*  152. Maximum Product Subarray
https://www.linkedin.com/in/jianminchen/
http://juliachencoding.blogspot.ca/
https://codereview.stackexchange.com/users/123986/jianmin-chen?tab=questions

https://www.linkedin.com/in/jianminchen

https://www.hackerrank.com/jianminchen_fl


maxp[n, n] matrix

maxp[i, j] = max(mapx

*/

// Complexity : n^2
int32_t maxSubProduct(const vector<int32_t> &input)
{
  int32_t maxp = numeric_limits<int32_t>::min();
  
  for (uint32_t i = 0; i < input.size(); ++i) {
    
    int32_t product = 1;
    for (uint32_t j = i; j < input.size(); ++j) {  // <- 
      product *= input[j];
      maxp = max(maxp, product);
    }    
  }
  
  return maxp;
}

// To execute C++, please define "int main()"
int main() {

  vector<int32_t> input{2, 3, -2, 4, -1};
  
  cout << maxSubProduct(input) << endl;   
  
  return 0;
}