Problem
Suppose you have an array of +ve numbers, -ve numbers and zeroes. Devise an algorithm to find the maximum contiguous subsequence product.
For 7 -3 -1 2 -40 0 3 6, the max subsequence product = -1 * 2 * -40 = 80
For -3 7 2 0 -5 7 -2 -2 2, the maximum subsequence product = -5 * 7 * -2 = 70
Solution
This is exhaustive method.
Find the product of all possible sub sequences, and select the max one.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the maximum contiguous subsequence product
Created Date :
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <iterator>
#include <algorithm>
using namespace std;
int CalcProd(int* arr, int len)
{
int prod = 1;
for(int i = 0; i < len; i++){
prod *= arr[i];
}
return prod;
}
int FindMaxSubSeqProduct(int* arr, int len)
{
int maxProd = 1;
int prod;
for(int i = 1; i < len + 1; ++i){
for(int j = 0; j < len - i + 1; ++j){
prod = CalcProd(arr + j, i);
if(prod > maxProd){
maxProd = prod;
}
}
}
return maxProd;
}
int main(int argc, char* argv[])
{
int testCases[][10] = {
{-1, 0, 1},
{1, -1, 0},
{0, -1, 1},
{7, -3, -1, 2, -40, 0, 3, 6},
{-3, 7, 2, 0, -5, 7, -2, -2, 2},
{0, 2, -2, -2, 3},
{-3, -2, 3, -3, -4, -5, -6, -7},
{-20, 10000, -20, 1}
};
int testCaseLens[] = {3, 3, 3, 8, 9, 5, 8, 4};
for(int i = 0; i < sizeof(testCases)/sizeof(testCases[0]); ++ i){
cout << "Test case " << i << endl;
copy(testCases[i], testCases[i] + testCaseLens[i],
ostream_iterator<int>(cout, " "));
cout << endl << "Max product is ";
cout << FindMaxSubSeqProduct(testCases[i], testCaseLens[i])
<< endl << endl;
}
return 0;
}
Output
Test case 0
-1 0 1
Max product is 1
Test case 1
1 -1 0
Max product is 1
Test case 2
0 -1 1
Max product is 1
Test case 3
7 -3 -1 2 -40 0 3 6
Max product is 80
Test case 4
-3 7 2 0 -5 7 -2 -2 2
Max product is 70
Test case 5
0 2 -2 -2 3
Max product is 24
Test case 6
-3 -2 3 -3 -4 -5 -6 -7
Max product is 15120
Test case 7
-20 10000 -20 1
Max product is 4000000
Press any key to continue . . .