onAugust 31, 2026

Kadane’s Algorithm: Maximum Product Subarray

Coding Interview Questions

1 min read

Problem Statement:

You are given a array with -ve integers.

You need to find the subarray with largest product and return the result

Example:

Input arr = [1, 2, 3, -3, 4]

Output: 6

Explanation: [2, 3]

Solution Explanation:

Solution is very simple using the kadane algorithm.

We will traverse from left to right and also traverse from right to left.

Then we will take the max of both.

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> arr) 
{
	int maxVal = INT_MIN;
    int prod = 1;

    for(int i = 0; i < arr.size(); i++)
    {
      prod *= arr[i];

      maxVal=max(prod,maxVal);
      
      if(prod == 0)
      	prod = 1;
    }

    prod=1;
    
    for(int i = arr.size()-1; i >= 0; i--)
    {
      prod *= arr[i];

      maxVal = max(prod,maxVal);
      
      if(prod == 0)
       	prod = 1;
    }
    return maxVal;
}

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