Problem : Given an array that contains both positive and negative integers, find the product of the maximum product subarray.
Discussion: It is a Similiar problem to maximum sum sub array problem.
Notice,maximum product can also be obtained by minimum (negative) product ending with the last element multiplied by this element.
we use mn_end_here(can be either a negative value or 1) and mx_end_here(can be either a positive value or 1)
So when we find a positive value we update the mx_end_here(multiply).
when we find a negative value mx_end_here will be either 1(as it cant be a negative value)
or multiplied value of mn_end_here with the new negative value.
and mn_end_here will be mx_end_here multiplied by new value(positive value multiplied by negative value will become a negative value.)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <stdio.h> int main() { //code int arr[15]; int mx_end_here,mn_end_here; int mx_so_far; int t,i,n,tmp; scanf("%d",&t); while(t--) { scanf("%d",&n); mx_so_far=1; mx_end_here=1; mn_end_here=1; for(i=0;i<n;i++) { scanf("%d",&arr[i]); if(arr[i]==0) { mn_end_here=1; mx_end_here=1; } else if(arr[i]>0) { mx_end_here=(mx_end_here*arr[i]>1?mx_end_here*arr[i]:1); mn_end_here=(mn_end_here*arr[i]<0?mn_end_here*arr[i]:1); } else if(arr[i]<0) { tmp=mx_end_here; mx_end_here=(mn_end_here*arr[i]>0?mn_end_here*arr[i]:1); mn_end_here=tmp*arr[i]; } if(mx_so_far<mx_end_here) mx_so_far=mx_end_here; } printf("%d\n",mx_so_far); } return 0; } |