maxproduct.cpp

#include <iostream>
#include <assert.h>
#include <stack>
using namespace std;
/*
 public class Solution {
 public int maxProduct(int[] A) {
 if (A == null || A.length == 0) {
 return 0;
 }
 int[] f = new int[A.length];
 int[] g = new int[A.length];
 f[0] = A[0];
 g[0] = A[0];
 int res = A[0];
 for (int i = 1; i < A.length; i++) {
 f[i] = Math.max(Math.max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
 g[i] = Math.min(Math.min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
 res = Math.max(res, f[i]);
 }
 return res;
 }
 }
 */
int maxproduct(int *arr, int n)
{
    int maxproduct = arr[0];
    int max = arr[0];
    int min = arr[0];
    
    for (int i = 1; i< n; ++i)
    {
        int temp = max;
        max = std::max( std::max( arr[i] * max, arr[i] ), arr[i] * min );
        min = std::min( std::min( arr[i] * temp, arr[i] ), arr[i] * min );
        maxproduct = std::max(max, maxproduct);
    }
    return maxproduct;
}

// Driver program to test abive function
int main()
{
    int a[] = {-2, -3, 0, -2, -40};
    
    cout<<maxproduct(a, sizeof(a)/sizeof(a[0]))<<endl;
    
    return 0;
}