22. Maximum product sub array

22. Maximum product sub array

Problem link :- click here

package programs;

import java.util.*;

public class Array__22
{

	static int maxProduct(int arr[], int n)
	{
		int product, max_product;
		int neg_flag, zero_flag;
		
		product = 1;
		max_product = 0;    //our final answer
		
		//neg_flag=0 -> no negative element
		//neg_flag=1  -> there is 1 negative element
		neg_flag = 0;
		int neg = 0;           //to store the negative element
		
		//zero_flag=0 -> at least there is one nonzero positive element
		//zero_flag=1  -> there are only nonzero elements and negative elements
		zero_flag = 1;
		
		for(int i=0; i<n; i++)
		{
			//if we come across zero in the middle 
			//then product till that element will be zero
			//so we will start multiplying from elements 
			//           next to zero from beginning
			if(arr[i]==0)
				product = 1;
			
			//if we come across a negative number 
			//then we don't multiply it to product
			//instead we store that element in a variable
			//and enable a flag to know that 
			//we are carrying a negative number
			else if(neg_flag==0 && arr[i]<0)
			{
				neg_flag = 1;
				neg = arr[i];
			}
			
			//if we are carrying a negative number and
			//come across with another negative element
			//then we multiply product with both negative element(1->we carrying, 2->arr[i])
			//and we disable that flag for next negative element
			else if(neg_flag==1 && arr[i]<0)
			{
				product = product * neg * arr[i];
				neg_flag = 0;
			}
			
			//if the element is positive then we multiply it with the product
			else
			{
				product = product * arr[i];
				//because we come across nonzero positive number
				zero_flag = 0;
			}
			
			//updating the maximum product in each step
			//because if we come across zero in any step
			//then from next step product will be 1 
			//and we start multiplying from beginning 
			//if we don't update then the maximum of that step will be lost
			max_product = Math.max(max_product, product);
		}
		
		//if we don't notice any positive element
		//and max_product is 1 (which we initialized when we
		//                                          come across zero)
		//which means that there is zero elements in the array
		//OR zero elements with only 1 negative element
		if(zero_flag==1  &&  max_product==1)
			return 0;
		return max_product;
	}
	
	public static void main(String[] args)
	{
		int n, i, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array :");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array :");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.println("Given Array : ");
		print_array(array);
		
		ans = maxProduct(array, n);
		System.out.println("\n\nMaximum Product is : "  + ans);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)