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