Maximum Product Subarray

Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be used.

Examples:

Input: arr[] = {6, -3, -10, 0, 2}
Output: 180 // The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output: 60 // The subarray is {60}

Input: arr[] = {-2, -3, 0, -2, -40}
Output: 80 // The subarray is {-2, -40}

C++:
01 int arrayMultiply(int A[], int start, int end)
02 {
03     if(start>end)
04         return 0;
05     int tmp=1;
06     while(start<=end){
07         tmp*=A[start++];
08     }
09     return tmp;
10 }
11 
12 void maxSubarray(int A[],int size, int& start, int& end, int& max)
13 {
14     int first=0;
15     int first_neg=-1;
16     int last_neg=-1;
17     int neg_cnt=0;
18     max=0;
19     start=end=0;
20     for(int i=0;i<=size;i++){
21         if((i==size)||(A[i]==0)){
22             if(neg_cnt%2==0){
23                     int tmp=arrayMultiply(A,first,i1);
24                     if(tmp>max){
25                         max=tmp;
26                         start=first;
27                         end=i1;
28                     }
29                 }
30             else if(neg_cnt%2==1){
31                     int tmpl=arrayMultiply(A,first,last_neg1);
32                     int tmpr=arrayMultiply(A,first_neg+1,i1);
33                     if(tmpl>max){
34                         max=tmpl;
35                         start=first;
36                         end=last_neg1;
37                     }
38                     if(tmpr>max){
39                         max=tmpr;
40                         start=first_neg+1;
41                         end=i1;
42                     }
43             }
44             first=i+1;
45             neg_cnt=0;
46         }else if(A[i]<0){
47             neg_cnt++;
48             if(first_neg<first)
49                 last_neg=first_neg=i;
50             else
51                 last_neg=i;
52         }
53     }
54 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s