Kadane’s Algorithm: Maximum Product Subarray

Problem Statement:

You are given an array with +ve, 0 ad -ve integers.

You need to find the maximum product subarray.

Example:

Input: arr[] = {1, 2, 3, -4, 5}

Output: 6

Explanation: [2, 3] has the largest product

Solution Explanation:

Similar to previous problems, instead of finding the max sum in the subarray, we will need to find max product.

In the array, negative numbers, there is a possibility of getting a larger number when multiplied fy another negative number.

Hence it is necessary to keep track of both maximum and minimum products.

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

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include<algorithm>

using namespace std;

int solution(vector<int>& nums) 
{
    int n = nums.size();
    int max_prod = nums[0];  
    int curr_max = nums[0]; 
    int curr_min = nums[0]; 
    
    for (int i = 1; i < n; i++) 
    {

        if (nums[i] < 0)
            swap(curr_max, curr_min);
        
        curr_max = max(nums[i], curr_max * nums[i]);
        curr_min = min(nums[i], curr_min * nums[i]);
        
        max_prod = max(max_prod, curr_max);
    }
    
    return max_prod;
}

int main()
{
    vector<int> arr =  {1, 2, 3, -4, 5};
  
    cout << solution(arr);
    return 0;
}

Output

6