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