• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

What matters is the number of negative values. If it's even return the entire array.

If 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

* 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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());
};``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.