Google Interview Question
Country: United States
public static void calcProd(int [] ints)
{
int posStart = 0;
int postEnd = ints.Length;
if(ints.Length < 2)
{
Console.WriteLine(ints[0]);
return;
}
if(ints.Length == 0)
{
Console.WriteLine(0);
return;
}
// int [] iList = {1,5,-6,88,5,-47,9,-65,6 };
int max = 0;
int runningTotal = 0;
int subArrayStart = 0;
int subArrayEnd = 0;
while (posStart < ints.Length)
{
runningTotal = calcSubArray(posStart, postEnd, ints);
if (runningTotal > max)
{
max = runningTotal;
subArrayStart = posStart;
subArrayEnd = postEnd;
}
posStart = posStart + 1;
}
posStart = 0;
while (postEnd > posStart)
{
runningTotal = calcSubArray(posStart, postEnd, ints);
if (runningTotal > max)
{
max = runningTotal;
subArrayStart = posStart;
subArrayEnd = postEnd;
}
postEnd = postEnd - 1;
}
Console.WriteLine($"Max is {max}");
Console.WriteLine($"start of subarray {subArrayStart} and end of subarray {subArrayEnd} ");
}
public static int calcSubArray(int posStart, int posEnd, int [] ints)
{
int runningtotal = 1;
for(int i = posStart; i < posEnd; i++)
{
runningtotal = runningtotal * ints[i];
}
Console.WriteLine(runningtotal);
return runningtotal;
}
public class MaxSubArrayProduct {
static class Data{
int product;
int startIndex;
int endIndex;
Data(){
super();
this.product = Integer.MIN_VALUE;
this.startIndex = -1;
this.endIndex = -1;
}
public Data(int product, int startIndex, int endIndex) {
super();
this.product = product;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
@Override
public String toString() {
return "Data [product=" + product + ", startIndex=" + startIndex + ", endIndex=" + endIndex + "]";
}
}
static Data ProcessSubArray(int[] arr, int startIndex, int endIndex){
if (startIndex == endIndex){
return new Data(arr[startIndex], startIndex, endIndex);
}else{
int val = 1;
int firstNegativeIndex = -1;
int lastNegativeIndex = -1;
for (int i=startIndex; i<=endIndex; i++){
val *= arr[i];
if (arr[i] <0){
if (firstNegativeIndex == -1){
firstNegativeIndex = i;
}
lastNegativeIndex = i;
}
}
if (val < 0){
int multiplierFirst = 1;
for (int j=startIndex; j<=firstNegativeIndex; j++){
multiplierFirst*=arr[j];
}
int multiplierLast = 1;
for (int j=lastNegativeIndex; j<=endIndex; j++){
multiplierLast*=arr[j];
}
if (val/multiplierFirst > val/multiplierLast){
startIndex = firstNegativeIndex+1;
val = val/multiplierFirst;
}else{
endIndex = lastNegativeIndex -1;
val = val/multiplierLast;
}
}
Data data = new Data(val, startIndex, endIndex);
return data;
}
}
private static void ProcessArr(int[] arr) {
if (arr == null || arr.length <=0){
System.out.println(new Data(Integer.MIN_VALUE, -1, -1));
return;
}
Data maxData = new Data();
int startIndex = -1;
for (int i=0; i<arr.length; i++){
if (arr[i] == 0){
if (startIndex != -1){
Data data = ProcessSubArray(arr, startIndex, i-1);
if (data.product>maxData.product){
maxData = data;
}
startIndex =-1;
}
if (0>maxData.product){
maxData = new Data(0, i, i);
}
} else {
if (startIndex == -1){
startIndex = i;
}
}
}
if (startIndex!=-1){
Data data = ProcessSubArray(arr, startIndex, arr.length-1);
if (data.product>maxData.product){
maxData = data;
}
}
System.out.println(maxData.toString());
}
public static void main(String[] args){
int arr[] = {0, 1, 2, -6, 8, 10, -9, -5, 1, 0, 8, 6, 5, 0};
ProcessArr(arr);
arr = new int[]{};
ProcessArr(arr);
arr = new int[]{0};
ProcessArr(arr);
arr = new int[]{-1};
ProcessArr(arr);
arr = new int[]{2};
ProcessArr(arr);
arr = new int[]{-3, 2};
ProcessArr(arr);
arr = new int[]{3, -2};
ProcessArr(arr);
arr = new int[]{-3, 2, 0, 0 , 3, -2};
ProcessArr(arr);
arr = new int[]{0, 0, -3, 2, 0, 0 , 3, -2, 0, 0};
ProcessArr(arr);
}
}
def get_max_indices(nums):
after_first_negative = 1
before_last_negative = 1
total = 1
first_negative_idx = None
last_negative_idx = None
for idx, num in enumerate(nums):
if num < 0:
last_negative_idx = idx
before_last_negative = total
if not first_negative_idx:
first_negative_idx = idx
if first_negative_idx and first_negative_idx != idx:
after_first_negative *= num
total *= num
if total > 0:
print(0, len(nums))
elif after_first_negative > before_last_negative:
print(first_negative_idx + 1, len(nums))
else:
print(0, last_negative_idx - 1)
print(max(total, after_first_negative, before_last_negative))
def get_max_indices(nums):
after_first_negative = 1
before_last_negative = 1
total = 1
first_negative_idx = None
last_negative_idx = None
for idx, num in enumerate(nums):
if num < 0:
last_negative_idx = idx
before_last_negative = total
if not first_negative_idx:
first_negative_idx = idx
if first_negative_idx and first_negative_idx != idx:
after_first_negative *= num
total *= num
if total > 0:
print(0, len(nums))
elif after_first_negative > before_last_negative:
print(first_negative_idx + 1, len(nums))
else:
print(0, last_negative_idx - 1)
print(max(total, after_first_negative, before_last_negative))
* This solution assumes extra iteration to calculate the array product first time.
1. Iterate over array.
2. Calculate the prod to the left of current element or right of current element.
3. Update the result with max.
int MaxProdSum::find(int *a, int n, int p, int &resI, int &resJ) {
int mxProd = INT_MIN;
int mxI = -1, mxJ = -1;
int curProd = 1;
for (int i = 0; i < n; i++) {
curProd *= a[i];
if (curProd > mxProd) {
mxProd = curProd;
mxI = 0;
mxJ = i;
}
if (p > mxProd) {
mxProd = p;
mxI = i;
mxJ = n - 1;
}
p /= a[i];
}
resI = mxI;
resJ = mxJ;
return mxProd;
}
def maxProduct(self, nums):
min_product_till_now = float('inf')
max_product_till_now = -float('inf')
max_so_far = -float('inf')
for item in nums:
if item < 0:
t1 = max(min_product_till_now * item, item)
t2 = min(max_product_till_now * item, item)
elif item > 0:
t1 = max(max_product_till_now * item, item)
t2 = min(min_product_till_now * item, item)
else:
t1, t2 = 0, 0
min_product_till_now, max_product_till_now = t2, t1
max_so_far = max(t1, t2, max_so_far)
return max_so_far
This solution is a modification of Kadane's algorithm which maintains two different sums namely max_till_now and min_till_now which are maximum and minimum till the current index.
This could easily be changed to find the indices.
pair<int, int> MaxProductSubarray(const vector<int>& a)
{
if (a.empty())
{
return pair<int, int>(-1, -1);
}
if (a.size() == 1)
{
return pair<int, int>(0, a.size());
}
int neg_num_count = 0;
int64_t l_prod = 1;
int l = 0;
for (; l < a.size(); ++l)
{
if (a[l] < 0)
{
++neg_num_count;
break;
}
l_prod *= a[l];
}
if (neg_num_count == 0)
{
return pair<int, int>(0, a.size());
}
int64_t r_prod = 1;
int r = a.size() - 1;
for (; r >= 0; --r)
{
if (a[r] < 0)
{
++neg_num_count;
break;
}
r_prod *= a[r];
}
if (l == r)
{
if (l == 0) {return pair<int, int>(l + 1, a.size());}
if (l == a.size() - 1) {return pair<int, int>(0, l);}
return l_prod > r_prod ? pair<int, int>(0, l) : pair<int, int>(l + 1, a.size());
}
for (int i = l + 1; i < r; ++i)
{
if (a[i] < 0)
{
++neg_num_count;
}
}
if (neg_num_count % 2 == 0)
{
return pair<int, int>(0, a.size());
}
return l_prod * -a[l] > r_prod * -a[r] ? pair<int, int>(0, r) : pair<int, int>(l + 1, a.size());
};
What matters is the number of negative values. If it's even return the entire array.
- gxg March 16, 2017If it's odd keep track of: first negative (position, value, product of positive subarray before it) and last negative (position, value, product of positive array after it).
If the product of first negative value and the positive subarray before it is smaller than the product of last negative value and the positive subarray after it the maximum product subarray is from 0 to last negative value (not included.)
Otherwise the maximum product subarray is from first negative (not included) to the end.
Edge case: positive subarray has zero length (original array starts and/or ends with negative value.) In this case the product of subarray is zero and we only need to look at the negative value itself.