Previously, I have posted about maximum interval sum. Now, unlike summation, product of an interval or segment is bit different.
Well, the problem is, from a given array of integers we have to determine the maximum product which can be found by any segment of the given array of integers.
Example:
Let, we have an array of these integers:
1 -2 4 -3 -1
So, the maximum interval product is 24 from 1 to -3 ( 1*-2*4*-3 ).
1 -2 4 0 -3 -1
Here, the maximum interval product is 4 from only 4.
Iteration:
Code:
Source:
http://acm.uva.es/board/viewtopic.php?f=33&t=11466&hilit=11059&sid=6ed77239e43f67e7ca9999e1412b0180
Well, the problem is, from a given array of integers we have to determine the maximum product which can be found by any segment of the given array of integers.
Example:
Let, we have an array of these integers:
1 -2 4 -3 -1
So, the maximum interval product is 24 from 1 to -3 ( 1*-2*4*-3 ).
1 -2 4 0 -3 -1
Here, the maximum interval product is 4 from only 4.
Iteration:
initial
|
1
|
-2
|
4
|
-3
|
-1
| |
mp
|
inf
|
1
|
inf
|
4
|
24
|
12
|
mn
|
inf
|
inf
|
-2
|
-8
|
-12
|
-24
|
mxProduct
|
-1
|
1
|
1
|
4
|
24
|
24
|
Code:
// Maximum Interval Product // Complexity: O(n) long long mxProduct = -1; // maximum product is stored. if unchanged, no valid product. long long t1, t2; long long mp = INF, mn = INF; // two counters for maxPositiveProduct and maxNegativeProduct for( i=0; i<N; i++ ) { scanf( "%d", &arr[i] ); if( arr[i] == 0 ) { if( mp != INF ) mxProduct = MAX( mxProduct, mp ); mp = mn = INF; continue; } if( mp==INF && mn==INF ) { arr[i] > 0 ? mp = arr[i] : mn = arr[i]; if( mp != INF ) mxProduct = MAX( mxProduct, mp ); continue; } if( mp == INF ) { if( arr[i] > 0 ) { mp = arr[i]; mn = arr[i] * mn; mxProduct = MAX( mxProduct, mp ); continue; } if( arr[i] < 0 ) { mp = arr[i] * mn; if( arr[i] >= mn ) mn = arr[i]; else mn = INF; mxProduct = MAX( mxProduct, mp ); continue; } } if( mn == INF ) { if( arr[i] < 0 ) { mn = arr[i] * mp; mp = INF; continue; } if( arr[i] > 0 ) { mp = arr[i] * mp; mn = INF; mxProduct = MAX( mxProduct, mp ); continue; } } t1 = arr[i] * mp; t2 = arr[i] * mn; if( arr[i] > 0 ) mp = t1, mn = t2; if( arr[i] < 0 ) mp = t2, mn = t1; mxProduct = MAX( mxProduct, mp ); }
Source:
http://acm.uva.es/board/viewtopic.php?f=33&t=11466&hilit=11059&sid=6ed77239e43f67e7ca9999e1412b0180
No comments:
Post a Comment