Kadane’s Algorithm: Maximum Product Subarray

Problem Statement:

Given an array with +ve, -ve and 0, you need to find the maximum product of continuous subarray.

Example:

Input: arr = [1, 2, 3]
Output: 6

Explanation: 1 * 2 * 3 = 6

Input: arr = [-4, 2, -3]
Output: 24

Explanation: -4 * 2 * -3 = 6

Solution Explanation:

In this problem we cannot use the Max subarry sum solution and replace with multiplication.

This is because of the -ve values.

So for that, we will use 2 variables, max_product and min_product.

When arr[i+1] is -ve and min_product is -ve, then multiplication of those two will be +ve and can be largest.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int solution(int arr[], int size) {
    
    int maxProduct = arr[0];
    int ith_max = arr[0];
    int ith_min = arr[0];
    
    for(int i=1; i<size; i++) {
        if(arr[i]<0) 
            swap(ith_max,ith_min);
            
        ith_max = max(arr[i], ith_max * arr[i]);
        ith_min = min(arr[i],ith_min * arr[i]);
        
        maxProduct = max(maxProduct, ith_max);
    }
    
    return maxProduct;
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    int max_sum = solution(arr, n);
    
    cout<< "Result = "<< max_sum;
    return 0;
}

Output

Result = 6