Walmart Labs Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
@alex, It's a simple iteration with bookkeeping. Keep track of the max contiguous product seen so far, as well as active prefixes for a new contiguous product. Negative numbers add the twist that you want pre_min as well as pre_max, since a negative number can temporarily flip a sequence to be negative, but you don't want to abandon it, in case a subsequent negative number flips the product back to positive.
If you set aside negative numbers for a bit, then this is the core logic for each iteration:
new_max = pre_max*elem
pre_max = max([elem, new_max])
ans = max([ans, pre_max])
Every iteration updates the best in-progress answer as well as the best overall answer to date (which could be still in progress or just getting started or encountered earlier in the list, before a zero or small fraction).
@showell: I think your algorithm gives the max product, not the corresponding range. right? correct me if i am wrong.
There are two issues that have to be taken into account while calculating the product and its corresponding range:
1) Number of zeroes in the array.
2) Total number of negative values in the array and number of negative numbers between zeros.
a) If total number of negative values is even and array doesn’t contain any zeros then the full range can be returned since the final result will be positive. E.g. { 6, 7, -8, 9, 8, -7, 6 }
b) If array contains zeroes then the number of negative values between zeroes has to be calculated to check whether they will give positive product (Is there even number of negative values between zeros). E.g. { 6, 7, 0, -6, 2, -7, 0, 8, -7, 6 } - -6 at index 3 and -7 at index 5 will give positive product.
To check the occurrence of zeros and negative values the algorithm does pre-processing of the original array ‘A’ and stores result in an additional array ‘B’ as follows: For any element A[i], B[i] contains number of negative values which are located after A[i]. E.g. A = { 6, 7, -8, 9, 8, -7, 6 } - > B={2, 2, 1, 1, 1, 0, 0}, A = { 6, 7, 0, -6, 2, -7, 0, 8, -7, 6 } -> B= {0, 0, 2, 1, 1, 0, 1, 1, 0, 0}.
Based on this the algorithm checks if the negative value can be include in the product or not. If the current A[i] is < 0 and B[i] >0 then A[i] is include in the product since we know that there is at least one more negative value and final result will be positive.
public static void main(String[] args) {
//int[] a = { 6, 7, -8, 9, 8, -7, 6 };
int[] a = { 6, 7, 0, -6, 2, -7, 0, 8, -7, 6 };
findProduct(a);
}
public static void findProduct(int[] a) {
int[] negValues = new int[a.length];
int numOfZeros = 0;
int numOfNegValues = a[a.length - 1] < 0 ? 1 : 0;
int totalNumOfNegValues = a[a.length - 1] < 0 ? 1 : 0;
int maxProd = 0;
int currentProd = 1;
int start = 0;
int currentStart = 0;
int end = 0;
for (int i = a.length - 2; i >= 0; i--) {
negValues[i] = numOfNegValues;
if (a[i] == 0) {
numOfZeros++;
numOfNegValues = 0;
} else if (a[i] < 0) {
totalNumOfNegValues++;
numOfNegValues++;
}
}
if (numOfZeros == a.length) {
System.out.println("Product is equal 0");
return;
}
if (numOfZeros == 0 && totalNumOfNegValues % 2 == 0) {
System.out.println("Full range");
return;
}
for (int i = 0; i < a.length; i++) {
if (a[i] == 0 || (a[i] < 0 && negValues[i] == 0 && currentProd > 0)) {
currentStart = i + 1;
currentProd = 1;
continue;
}
currentProd *= a[i];
if (currentProd > maxProd) {
maxProd = currentProd;
start = currentStart;
end = i;
}
}
System.out.println("Start: " + start + ", end: " + end + ", prod: " + maxProd);
}
The question is confusing to me. Maximum product is multiplying two consecutive maximum values (both positive or both negative numbers). So, just sort the array and find the two consecutive positive, or negative numbers. Whichever of these is maximum is the maximum product. What has range got to do with it?
The problem allows you to use more than two numbers in the product, as long as they're contiguous. Also, it's not explicitly stated, but I'm assuming that a range of one integer can be considered to have a "product" of itself.
Multiplication is commutative, so 5*7*2*3 is not ambiguous.
Also, multiplication has an identity element, so it's reasonable to consider product([42]) to be 42*1, although you'd clarify that with the interviewer.
Last but not least, you need clarify whether the product of an empty range is considered to be 1 or undefined. A mathematician would probably choose 1, but the engineering context might make undefined be more appropriate.
This is the solution to get the range. My code assumes there's no 0 in the range. I will work on that too. The code should be self-explanatory.
#include <iostream>
using namespace std;
int main (){
int arr[]={6,-7,8,-9,8,-7,6};
int arrSize = sizeof(arr)/sizeof(int);
int arrProduct=1;
for (int i=0;i<arrSize;i++){
arrProduct*=arr[i];
}
int LHSProduct=1;
int RHSProduct=arrProduct;
int largestProduct=0;
int startRange =0, endRange = 0;
for (int i=0;i<arrSize;i++){
LHSProduct*=arr[i];
RHSProduct/=arr[i];
largestProduct = (LHSProduct>largestProduct) ? (startRange=0,endRange=i,LHSProduct) : largestProduct;
largestProduct = (RHSProduct>largestProduct) ? (startRange=i,endRange=arrSize-1,RHSProduct) : largestProduct;
}
for (int i = startRange;i<=endRange;i++){
cout << arr[i] << ", ";
}
cout << endl;
return 0;
}
public void maxProduct(int[] arr) {
boolean isNegative = false;
int maxproduct = 1;
int maxProductTemp = 1;
int negativeProduct = 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {// negative
isNegative = true;
negativeProduct=maxProductTemp;
negativeProduct *= arr[i];
if (maxproduct < maxProductTemp) {
maxproduct = maxProductTemp;
}
maxProductTemp = 1;
} else if (arr[i] > 0) {// positive
if (isNegative) {
negativeProduct *= arr[i];
}
maxProductTemp *= arr[i];
} else {// 0
if (maxproduct < maxProductTemp) {
maxproduct = maxProductTemp;
}
maxProductTemp = 1;
}
}
maxProductTemp = (maxProductTemp > negativeProduct) ? maxProductTemp
: negativeProduct;
maxproduct = (maxProductTemp > maxproduct) ? maxProductTemp
: maxproduct;
System.out.println(" >> " + maxproduct);
}
public void maxProduct(int[] arr) {
boolean isNegative = false;
int maxproduct = 1;
int maxProductTemp = 1;
int negativeProduct = 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {// negative
isNegative = true;
negativeProduct=maxProductTemp;
negativeProduct *= arr[i];
if (maxproduct < maxProductTemp) {
maxproduct = maxProductTemp;
}
maxProductTemp = 1;
} else if (arr[i] > 0) {// positive
if (isNegative) {
negativeProduct *= arr[i];
}
maxProductTemp *= arr[i];
} else {// 0
if (maxproduct < maxProductTemp) {
maxproduct = maxProductTemp;
}
maxProductTemp = 1;
}
}
maxProductTemp = (maxProductTemp > negativeProduct) ? maxProductTemp
: negativeProduct;
maxproduct = (maxProductTemp > maxproduct) ? maxProductTemp
: maxproduct;
System.out.println(" >> " + maxproduct);
}
Check from front and from back!
public class MaxProd{
public static void MaxProduct(int [] arr){
int bestend=-1;;
int maxProd1=1;
int curProd=1;
int strt1=0;
// Find first non-zero start
for(int i=0;i<arr.length;i++){
if(arr[i]!=0){
strt1=i;
break;
}
}
for(int i=strt1;i<arr.length;i++){
curProd*=arr[i];
if(curProd>=maxProd1){
bestend=i;
maxProd1=curProd;
}
}
int beststrt=-1;
int maxProd2=1;
curProd=1;
int end1=arr.length-1;
for(int i=arr.length-1;i>=0;i--){
if(arr[i]!=0) {
end1=i;
break;
}
}
for(int i=end1;i>=0;i--){
curProd*=arr[i];
if(curProd>=maxProd2){
beststrt=i;
maxProd2=curProd;
}
}
if(maxProd1>=maxProd2){
System.out.println("Best Product="+maxProd1+" From "+strt1+" to "+bestend);
}else{
System.out.println("Best Product="+maxProd2+" From "+beststrt+" to "+end1);
}
}
public static void main(String [] args){
int [] arr={1,-2,3,-4,5,-6};
MaxProduct(arr);
}
}
As someone mentioned above:
1 - We are looking for a sequence of three consecutive numbers in the array
2 - The array is not sorted, so there can be any positive and negative number sequence
public void findGreatestProduct(List<Integer> list) {
Integer greatestProduct = Integer.MIN_VALUE;
Integer greatestAbsoluteSum = 0;
Integer currentAbsoluteSum = 0;
boolean positive = false;
Integer[] n = new Integer[3];
Integer[] current = new Integer[3];
if (list == null || list.size() < 3) {
System.out.println("The list is to short or empty!");
}
current[0] = current[1] = current[2] = 0;
for (int i = 0; i < list.size() - 2; i++) {
n[0] = list.get(i);
n[1] = list.get(i + 1);
n[2] = list.get(i + 2);
if (n[0] != 0 && n[1] != 0 && n[2] != 0) {
positive = ((( n[0] < 0 ? 1 : 0 ) + ( n[1] < 0 ? 1 : 0 ) + ( n[2] < 0 ? 1 : 0 )) % 2 == 0);
if (positive) {
currentAbsoluteSum = Math.abs(n[0]) + Math.abs(n[1]) + Math.abs(n[2]);
if (currentAbsoluteSum > greatestAbsoluteSum) {
greatestAbsoluteSum = currentAbsoluteSum;
current[0] = n[0];
current[1] = n[1];
current[2] = n[2];
}
}
}
}
greatestProduct = current[0] * current[1] * current[2];
System.out.println( current[0] + " * " + current[1] + " * " + current[2] + " = " + greatestProduct);
}
If the absolute sum of three values is the biggest, it's product will be de biggest given that the number of negative values is even. For that I calculate for all triples of values:
1 - Skip if one of the values is 0
2 - Is the number of negative values even (negative * negative = positive)
3 - Is the sum of absolute values the greatest, then the product will be the greatest too
As someone mentioned above:
1 - We are looking for a sequence of three consecutive numbers in the array
2 - The array is not sorted, so there can be any positive and negative number sequence
public void findGreatestProduct(List<Integer> list) {
Integer greatestProduct = Integer.MIN_VALUE;
Integer greatestAbsoluteSum = 0;
Integer currentAbsoluteSum = 0;
boolean positive = false;
Integer[] n = new Integer[3];
Integer[] current = new Integer[3];
if (list == null || list.size() < 3) {
System.out.println("The list is to short or empty!");
}
current[0] = current[1] = current[2] = 0;
for (int i = 0; i < list.size() - 2; i++) {
n[0] = list.get(i);
n[1] = list.get(i + 1);
n[2] = list.get(i + 2);
if (n[0] != 0 && n[1] != 0 && n[2] != 0) {
positive = ((( n[0] < 0 ? 1 : 0 ) + ( n[1] < 0 ? 1 : 0 ) + ( n[2] < 0 ? 1 : 0 )) % 2 == 0);
if (positive) {
currentAbsoluteSum = Math.abs(n[0]) + Math.abs(n[1]) + Math.abs(n[2]);
if (currentAbsoluteSum > greatestAbsoluteSum) {
greatestAbsoluteSum = currentAbsoluteSum;
current[0] = n[0];
current[1] = n[1];
current[2] = n[2];
}
}
}
}
greatestProduct = current[0] * current[1] * current[2];
System.out.println( current[0] + " * " + current[1] + " * " + current[2] + " = " + greatestProduct);
}
If the absolute sum of three values is the biggest, it's product will be de biggest given that the number of negative values is even. For that I calculate for all triples of values:
1 - Skip if one of the values is 0 (could be optimized to skip 2 if n[2] is 0)
2 - Is the number of negative values even (negative * negative = positive)?
3 - If the sum of absolute values the greatest, then the product will be the greatest too
#include <iostream>
#include <cstdio>
using namespace std;
int sum_max(int a[],int l)
{
int i,Product=1,smal= -1000000;
for(i=0;i<l;i++)
{
if(a[i]<0)
{
if(a[i]>=smal)
{
smal=a[i];
}
Product *=a[i];
}
else if(a[i] !=0)
{
Product *=a[i];
}
}
if(Product<0)
{
return Product/smal;
}
else
{
return Product;
}
}
int main()
{
int a[]={-2,-3,4,-1,-2,1,5,-3};
cout<<sum_max(a,8)<<endl;
}
public class MaxContiguousProduct {
public static void main(String[] args) {
System.out
.println(0 == findMaxContProd(new int[] { 0, 0, -2, 0, 0, 0 }));
System.out.println(8 == findMaxContProd(new int[] { -2, 1, 1, 8 }));
System.out.println(18 == findMaxContProd(new int[] { -2, -3, 1, 3 }));
System.out
.println(12 == findMaxContProd(new int[] { -3, -4, 0, 1, 2, 3 }));
System.out.println(720 == findMaxContProd(new int[] { 1, -1, 10, -8,
-9, 0 }));
System.out.println(2 == findMaxContProd(new int[] { -50, 1, 2 }));
System.out.println(2 == findMaxContProd(new int[] { -50, 2, 1 }));
}
private static int findMaxContProd(int a[]) {
int prodMaxGlobal = 0, prodMaxLocalPositive = 0, prodMaxLocalNegative = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] < 0) {
if (prodMaxLocalNegative == 0) {
if (prodMaxLocalPositive == 0) {
prodMaxLocalNegative = a[i];
} else {
prodMaxLocalNegative = prodMaxLocalPositive * a[i];
if (prodMaxGlobal < prodMaxLocalPositive) {
prodMaxGlobal = prodMaxLocalPositive;
}
prodMaxLocalPositive = 0;
}
} else {
if (prodMaxLocalPositive == 0) {
prodMaxLocalPositive = prodMaxLocalNegative * a[i];
prodMaxLocalNegative = a[i];
} else {
int tmp = prodMaxLocalNegative;
prodMaxLocalNegative = prodMaxLocalPositive * a[i];
prodMaxLocalPositive = tmp * a[i];
}
}
} else if (a[i] > 0) {
if (prodMaxLocalPositive == 0) {
if (prodMaxLocalNegative == 0) {
prodMaxLocalPositive = a[i];
} else {
prodMaxLocalPositive = a[i];
prodMaxLocalNegative = 0;
}
} else {
if (prodMaxLocalNegative == 0) {
prodMaxLocalPositive = prodMaxLocalPositive * a[i];
} else {
prodMaxLocalPositive = prodMaxLocalPositive * a[i];
prodMaxLocalNegative = prodMaxLocalNegative * a[i];
}
}
} else {
if (prodMaxGlobal < prodMaxLocalPositive) {
prodMaxGlobal = prodMaxLocalPositive;
}
prodMaxLocalPositive = 0;
prodMaxLocalNegative = 0;
}
}
if (prodMaxGlobal < prodMaxLocalPositive) {
prodMaxGlobal = prodMaxLocalPositive;
}
return prodMaxGlobal;
}
}
public class MaxContiguousProduct {
public static void main(String[] args) {
System.out
.println(0 == findMaxContProd(new int[] { 0, 0, -2, 0, 0, 0 }));
System.out.println(8 == findMaxContProd(new int[] { -2, 1, 1, 8 }));
System.out.println(18 == findMaxContProd(new int[] { -2, -3, 1, 3 }));
System.out
.println(12 == findMaxContProd(new int[] { -3, -4, 0, 1, 2, 3 }));
System.out.println(720 == findMaxContProd(new int[] { 1, -1, 10, -8,
-9, 0 }));
System.out.println(2 == findMaxContProd(new int[] { -50, 1, 2 }));
System.out.println(2 == findMaxContProd(new int[] { -50, 2, 1 }));
}
private static int findMaxContProd(int a[]) {
int prodMaxGlobal = 0, prodMaxLocalPositive = 0, prodMaxLocalNegative = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] < 0) {
if (prodMaxLocalNegative == 0) {
if (prodMaxLocalPositive == 0) {
prodMaxLocalNegative = a[i];
} else {
prodMaxLocalNegative = prodMaxLocalPositive * a[i];
if (prodMaxGlobal < prodMaxLocalPositive) {
prodMaxGlobal = prodMaxLocalPositive;
}
prodMaxLocalPositive = 0;
}
} else {
if (prodMaxLocalPositive == 0) {
prodMaxLocalPositive = prodMaxLocalNegative * a[i];
prodMaxLocalNegative = a[i];
} else {
int tmp = prodMaxLocalNegative;
prodMaxLocalNegative = prodMaxLocalPositive * a[i];
prodMaxLocalPositive = tmp * a[i];
}
}
} else if (a[i] > 0) {
if (prodMaxLocalPositive == 0) {
if (prodMaxLocalNegative == 0) {
prodMaxLocalPositive = a[i];
} else {
prodMaxLocalPositive = a[i];
prodMaxLocalNegative = 0;
}
} else {
if (prodMaxLocalNegative == 0) {
prodMaxLocalPositive = prodMaxLocalPositive * a[i];
} else {
prodMaxLocalPositive = prodMaxLocalPositive * a[i];
prodMaxLocalNegative = prodMaxLocalNegative * a[i];
}
}
} else {
if (prodMaxGlobal < prodMaxLocalPositive) {
prodMaxGlobal = prodMaxLocalPositive;
}
prodMaxLocalPositive = 0;
prodMaxLocalNegative = 0;
}
}
if (prodMaxGlobal < prodMaxLocalPositive) {
prodMaxGlobal = prodMaxLocalPositive;
}
return prodMaxGlobal;
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/***Solution steps
1.First find the product of all the numbers while calculating the product capture the negative indices in some arraylist
2.After calculating the product then check the prod is +ve or -ve if negative check the the 1st -ve nad last -ve number and which number is less and divide with taht number simple
**/
package javaapplication1;
/**
*
* @author midhulak
*/
import java.util.*;
public class Prodmax {
public int TwoLargeNumbers(int[] a){
int prodmax=1;
ArrayList<Integer> al = new ArrayList<Integer>();
for(int i=0;i<=a.length-1;i++){
String num = a[i]+"";
if(num.contains("-")){
al.add(i);
}
prodmax=prodmax*a[i];
}
String result=prodmax+"";
if(result.contains("-")){
int firstnegative = al.get(0);
int lastnegative = al.get(al.size()-1);
if(a[firstnegative] > a[lastnegative])
prodmax= prodmax/a[firstnegative];
else
prodmax=prodmax/a[lastnegative];
}
return prodmax;
}
public static void main(String a[]){
int list[] = {-1,2,3,-4,};
Prodmax t = new Prodmax();
System.out.println(t.TwoLargeNumbers(list));
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/***Solution steps
1.First find the product of all the numbers while calculating the product capture the negative indices in some arraylist
2.After calculating the product then check the prod is +ve or -ve if negative check the the 1st -ve nad last -ve number and which number is less and divide with taht number simple
**/
package javaapplication1;
/**
*
* @author midhulak
*/
import java.util.*;
public class Prodmax {
public int TwoLargeNumbers(int[] a){
int prodmax=1;
ArrayList<Integer> al = new ArrayList<Integer>();
for(int i=0;i<=a.length-1;i++){
String num = a[i]+"";
if(num.contains("-")){
al.add(i);
}
prodmax=prodmax*a[i];
}
String result=prodmax+"";
if(result.contains("-")){
int firstnegative = al.get(0);
int lastnegative = al.get(al.size()-1);
if(a[firstnegative] > a[lastnegative])
prodmax= prodmax/a[firstnegative];
else
prodmax=prodmax/a[lastnegative];
}
return prodmax;
}
public static void main(String a[]){
int list[] = {-1,2,3,-4,};
Prodmax t = new Prodmax();
System.out.println(t.TwoLargeNumbers(list));
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;
/**
*
* @author midhulak
*/
import java.util.*;
public class Prodmax {
public int TwoLargeNumbers(int[] a){
int prodmax=1;
ArrayList<Integer> al = new ArrayList<Integer>();
for(int i=0;i<=a.length-1;i++){
String num = a[i]+"";
if(num.contains("-")){
al.add(i);
}
prodmax=prodmax*a[i];
}
String result=prodmax+"";
if(result.contains("-")){
int firstnegative = al.get(0);
int lastnegative = al.get(al.size()-1);
if(a[firstnegative] > a[lastnegative])
prodmax= prodmax/a[firstnegative];
else
prodmax=prodmax/a[lastnegative];
}
return prodmax;
}
public static void main(String a[]){
int list[] = {-1,2,3,-4,};
Prodmax t = new Prodmax();
System.out.println(t.TwoLargeNumbers(list));
}
}
package javaapplication1;
/**
*
* @author midhulak
*/
import java.util.*;
public class Prodmax {
public int TwoLargeNumbers(int[] a){
int prodmax=1;
ArrayList<Integer> al = new ArrayList<Integer>();
for(int i=0;i<=a.length-1;i++){
String num = a[i]+"";
if(num.contains("-")){
al.add(i);
}
prodmax=prodmax*a[i];
}
String result=prodmax+"";
if(result.contains("-")){
int firstnegative = al.get(0);
int lastnegative = al.get(al.size()-1);
if(a[firstnegative] > a[lastnegative])
prodmax= prodmax/a[firstnegative];
else
prodmax=prodmax/a[lastnegative];
}
return prodmax;
}
public static void main(String a[]){
int list[] = {-1,2,3,-4,};
Prodmax t = new Prodmax();
System.out.println(t.TwoLargeNumbers(list));
}
}
package com.motorola.globalnotificationservice.test;
import java.util.*;
public class Prodmax {
public int TwoLargeNumbers(int[] a) {
int prodmax = 1;
ArrayList<Integer> al = new ArrayList<Integer>();
for (int i = 0; i <= a.length - 1; i++) {
String num = a[i] + "";
if (num.contains("-")) {
al.add(i);
}
prodmax = prodmax * a[i];
}
String result = prodmax + "";
if (result.contains("-")) {
int firstnegative = al.get(0);
int lastnegative = al.get(al.size() - 1);
if (a[firstnegative] > a[lastnegative])
prodmax = prodmax / a[firstnegative];
else
prodmax = prodmax / a[lastnegative];
}
return prodmax;
}
public static void main(String a[]) {
int list[] = { -1, 2, 3, -4, };
Prodmax t = new Prodmax();
System.out.println(t.TwoLargeNumbers(list));
}
}
#define ASZ 5
int a[ASZ] = { 2, 1, 3, -2, 7};
int findprod(int *a, int s, int e)
{
int prod = a[s];
for(int i = s+1; i<e; i++)
{
prod *= a[i];
}
return prod;
}
int maxseq(int *a, int s, int e)
{
int cneg = 0, fneg = 0, lneg = 0;
for(int i = s; i < e; i++)
{
if(a[i] < 0)
{
if(!fneg)
fneg = i;
lneg = i;
cneg++;
}
}
if(cneg%2 == 0)
return findprod(a, s, e);
return max(findprod(a, fneg+1, e), findprod(a, s, lneg -1));
}
int main(int argc, char *argv[])
{
printf("The max seq prod = %d\n", maxseq(a, 0, ASZ));
printf("Done\n");
return 0;
}
void maxproduct( int num[], int length)
{
int currStart, currEnd, maxStart, maxEnd;
double currProd, prevProd, maxProd;
prevProd = currProd = maxProd = num[0] // assuming non empty array, add checks
currStart = 0;
currEnd = -1;
int i = 1;
for( ; i < length; i++)
{
currProd = currProd * num[i];
if(currProd < prevProd)
{
currEnd = i;
if( prevProd > maxProd)
{
maxStart = currStart;
maxEnd = currEnd;
maxProd = prevProd;
}
currStart = i;
currProd = num[i];
}
prevProd = currProd;
}
if(currEnd == -1 || currEnd < currStart)
{
currEnd = i;
if (currProd > maxProd)
{
maxStart = currStart;
maxEnd = currEnd;
maxProd = currProd;
}
}
cout << "Range is : "<<maxStart<<" - "<<maxEnd<<" = "<<maxProd<<endl;
}
yup.. didn't test it before posting it. Thanks for pointing out. Corrected now.
void maxproduct( int num[], int length)
{
if(length >= 1)
{
int currStart, currEnd, maxStart, maxEnd;
double currProd, prevProd, maxProd;
prevProd = currProd = maxProd = num[0];
currStart = 0;
currEnd = -1;
int i = 1;
for( ; i < length; i++)
{
currProd = currProd * num[i];
if(currProd < prevProd)
{
currEnd = i;
if( prevProd > maxProd)
{
maxStart = currStart;
maxEnd = currEnd-1;
maxProd = prevProd;
}
currStart = i;
currProd = num[i];
}
prevProd = currProd;
}
if (currProd > maxProd) // if the value at the end is greater...
{
maxStart = currStart;
maxEnd = i-1;
maxProd = currProd;
}
cout << "Range is : "<<maxStart<<" - "<<maxEnd<<" = "<<maxProd<<endl;
}
else
{
cout << "Empty Array"<<endl;
}
}
If i am getting the question correctly, I think if the range is {6,7,-8,9,8,-7,6}, the whole range should be returned. product of two negative numbers is positive, so the whole range gives the largest possible product.
kadanes algo ..
keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values.
void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
int maxSumSoFar = -2147483648;
int curSum = 0;
int a = b = s = i = 0;
for( i = 0; i < len; i++ ) {
curSum += array[i];
if ( curSum > maxSumSoFar ) {
maxSumSoFar = curSum;
a = s;
b = i;
}
if( curSum < 0 ) {
curSum = 0;
s = i + 1;
}
}
*start = a;
*end = b;
*maxSum = maxSumSoFar;
}
O(n)
This same question was asked pretty recently. Here is my solution:
- showell30@yahoo.com March 16, 2013def max_product(a): ans = pre_max = pre_min = a[0] for elem in a[1:]: new_min = pre_min*elem new_max = pre_max*elem pre_min = min([elem, new_max, new_min]) pre_max = max([elem, new_max, new_min]) ans = max([ans, pre_max]) return ans assert 0 == max_product([0,0,-2,0,0,0]) assert 8 == max_product([-2,1,1,8]) assert 18 == max_product([-2,-3,1,3]) assert 12 == max_product([-3,-4,0,1,2,3]) assert 720 == max_product([1,-1,10,-8, -9, 0]) assert 2 == max_product([-50, 0.5, 2]) assert 2 == max_product([-50, 2, 0.5])