Maximum Interval Product

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:

	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

Longest Palindromic Subsequence or Maximum Length of Palindrome

Definition:
              A sequence is called "Palindrome" if it is read same left to right and right to left. The sequence remains same as before after reversing it. The sequence "MADAM" is a Palindrome.
More about Palindrome.

A sequence which is a Palindrome is called a Palindromic Sequence. In this problem, given any sequence (not necessarily palindromic sequence), and we have to determine the Longest Palindromic Sub-sequence of Maximum Length of Palindrome of it.
A dynamic approach is not mandatory for this problem, because there is no overlapping sub-problems and so no optimal sub-structure available for Longest Palindromic Sub-sequence.
But if we go recursively, it can be easily determined. How? Obviously there is no overlapping sub-problems but we can divide it into sub-problems (that how we do it :p).
Here is a C++ solution for LPS.

#include <iostream>
#include <string>

using namespace std;

template<class T>inline T MAX( T a, T b ){ return a>b ? a:b; } // Note: returns maximum of a and b

string A;

int LPS( int i, int j ) {
    if( i == j ) return 1; // A[i] & A[j] are same, cost is 1
    if( i > j ) return 0;
    if( A[i] == A[j] )
        return 2 + LPS( i+1, j-1 ); // A[i] & A[j] are different, cost is 2, 1 for each.
    else
        return MAX( LPS(i+1, j), LPS(i, j-1) );
}

int main( ){
    while( cin >> A ){
        int len = A.length( );
        int res = LPS(0, len);
        cout << "Longest Palindromic Subsequence is: " << res << endl;
    }
    return 0;
}

Obviously, a memoization make the procedure lot more faster. Here is a memoized faster version.

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

template<class T>inline T MAX( T a, T b ){ return a>b ? a:b; } // Note: returns maximum of a and b
const int SIZ = 105;

#define mset2d(x,n) memset(x,n,sizeof(int [SIZ][SIZ]))

string A;
int memo[SIZ][SIZ];

int LPS( int i, int j ) {
    if( i == j ) return 1; // A[i] & A[j] are same, cost is 1
    if( i > j ) return 0;
    if( memo[i][j] != -1 ) return memo[i][j];
    if( A[i] == A[j] )
        memo[i][j] = 2 + LPS( i+1, j-1 ); // A[i] & A[j] are different, cost is 2, 1 for each.
    else
        memo[i][j] = MAX( LPS(i+1, j), LPS(i, j-1) );
    return memo[i][j];
}

int main( ){
    while( cin >> A ){
        mset2d( memo, -1 );
        int len = A.length( );
        int res = LPS(0, len);
        cout << "Longest Palindromic Subsequence is: " << res << endl;
    }
    return 0;
}

Maximum Interval Sum

Given a array of natural numbers, we have to find the maximum interval sum.
5    5   -1    5    5
Now we have these intervals (5 + 5), ( 5 + 5 + (-1)), (5 + 5 + (-1) + 5), (5 + 5 + (-1) + 5 + 5). 
Which interval has maximum sum?
(5 + 5) = 10
( 5 + 5 + (-1)) = 9
(5 + 5 + (-1) + 5) = 14
(5 + 5 + (-1) + 5 + 5) = 19
So, the last interval has maximum sum. These type of problems are called Maximum Interval Sum.
C++ implementation:

#include <iostream>
using namespace std;
const int INF = (-(1<<30));  // negative infinity
int MIS( ) {
    sum = 0; // initially sum is 0
    Max = -INF; // Maximum is less than 0
    for( i=0; i<N; i++ ) {
       sum += A[i]; // "A[]" array of intejars
        if( sum > Max ) Max = sum;
        if( sum < 0 ) sum = 0;  // sum below 0 is not useful, right?
    }
    return Max;
}

Maximum Sum Sub Matrix

Problem:

        Given m*n matrix. We have to find a sub-matrix which have maximum sum. Values of the matrix can be both positive and negative.

Idea:

      Lets start with an example then we will generate our idea. Suppose we have 4*4 matrix as below:
    [ initial matrix ] 
-1      2     3      10          
 5      9    -7       6
 0    -1     -3     -5
 7     5   -18       2

Now we add first column with second column. So, the matrix became like this:
-1      1     3      10
 5     14    -7       6
 0    -1     -3     -5
 7    12   -18       2
Now add second column with third column and the third column with last column. Then, the matrix will look like:
-1      1     4      14
 5     14     7      13
 0    -1     -4      -9
 7    12    -6      -4

Now the row addition part. Add first row with second, then add second with third, then third with last. Finally, the matrix will be:
-1      1      4      14
 5     15    11     27
 0     14     7      18
 7     26     1      14

Our matrix is ready to manipulate.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Definitely, we can say form this matrix that value of every cell is the sum of (0,0) to that cell. Say, (1,1) is 15 is the sum of (0,0), (0,1), (1,0) and (1,1) cells that is 15 i.e. ( -1+2+5+9 ) = 15. This property makes our idea easier. 

       In this matrix, the maximum sum is the middle sub-matrix. ( 15 + 11 + 14 + 7 ) = 37.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

We are very closer to our solution. Now, see carefully. Cell (2,2) has cumulative sum form cell (0,0) to (2,2).  

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

We can subtract the sum of cell (0,0) to (0,2) from this result. 

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Again, we subtract sum of cell (0,0) to (2, 0) from the last result.

-1	1	4	14
4	15	11	27
4	14	7	18
11	26	1	14

Have we finished ? No. Look at the matrix above carefully. We have subtract cell (0,0) from the actual result  twice. It should be once. Finally, add the (0,0) cell to actual result and we get our maximum sum sub-matrix.