Sunday, May 3, 2015

Maximize the number of magical gems by passing through array of house

Problem
There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even.

Example
Gem array = 1 2 0 4 5 6 2 3
color array = 0 0 1 1 1 0 0 1 (r=1,b=0)
o/p = 20 (4*5)

Solution

This is similar to maximum product subarray, but there is another condition of red color.

Here is the code below:
int maximumMoney(int n, int[] colour, int[] gems) {
    int max = 1;
    int red = 0;
    int start = 0, end = 0;
    int actualMax=1;
    for(int i=0;i<gems.length;i++){
        if(gems[i]>0)
        {
            max = max*gems[i];
            end++;
            if(colour[i] == 1)
               red++;
            
               
        }else{
            if(actualMax < max){
                if(red%2==0)
                {
                    actualMax = max;

                }else{
                    int temp = max;
                    int startRed = -1, endRed = -1;
                    for(int i=start;i<end;i++){
                        if(colour[i]==1 && startRed==-1){
                           startRed = i;
                           endRed = i;
                        }else if(colour[i]==1)
                            endRed = i;
                    }
                    int tempProdStart = 1; tempEndProd = 1;
                    for(int i=start;i<=startRed;i++){
                        tempProdStart = a[i]*tempProdStart ;
                        
                    }
                    
                     for(int i=endRed;i<=end;i++){
                        tempEndProd= a[i]*tempEndProd;
                        
                    }
                    int minProd = Math.min(tempProdStart, tempEndProd);
                    
                    max = temp/minProd;
                    if(max > actualMax){
                        actualMax = max;
                    }
                        
                    
                }
                   
            }
              
            start = end+1;
            end = end + 1;
            
        }
    }
}

Time complexity - O(n)



0 comments:

Post a Comment