Use the algorithm in the book intro to algorithm has Memory Limit Exceeded problem


  • 0
    C

    Very weird...
    on P72 of the MIT book intro to algorithm


  • 0
    S

    Could you please post the code here, with some explanation of the algorithm idea?


  • 0
    C
    This post is deleted!

  • 0
    S

    @ceresgu's previous comment. Please leave long code post as an answer, or it will be messy.

    struct sumIndex{
    int low;
    int high;
    int sumValue;
    };

    class Solution {
        
    public:
        sumIndex findMaxCross(vector<int> changes, int low, int mid, int high){
            int leftSum= -std::numeric_limits<int>::max();
            int sum=0;
            int maxLeft;
            for(int i=mid; i>=low; i--){
                sum += changes[i];
                if (sum>leftSum){
                    leftSum=sum;
                    int maxLeft=i;
                }
            }
            int rightSum= -std::numeric_limits<int>::max();
            sum=0;
            int maxRight;
            for (int j=mid+1;j<=high;j++){
                sum +=changes[j];
                if (sum>rightSum){
                    rightSum=sum;
                    int maxRight=j;
                    
                }
            }
            sumIndex cross;
            cross.low=maxLeft;
            cross.high=maxRight;
            cross.sumValue=leftSum+rightSum;
            return cross;
            }
            
            
            
        sumIndex findMax(vector<int> changes, int low, int high){
            sumIndex result;
            sumIndex left, right, cross;
            if(low==high){
                result.low=low;
                result.high=high;
                result.sumValue=changes[low];
            }
            else{
                int mid =(low+high)/2;
                left= findMax(changes, low, mid);
                right=findMax(changes, mid+1, high);
                cross=findMaxCross(changes,low, mid, high);
                
                if (left.sumValue>right.sumValue && left.sumValue>cross.sumValue)
                    result=left;
                else if(right.sumValue>left.sumValue && right.sumValue>cross.sumValue)
                    result=right;
                else
                    result=cross;
            }
            
            return result;
        }
    
        int maxProfit(vector<int> &prices) {
            
            vector<int> changes;
            
            changes.push_back(0);
            for (int i=1; i<prices.size(); i++)
                changes.push_back(prices[i]-prices[i-1]);
            
            return findMax(changes, 0, changes.size()-1).sumValue;
            }
    };
    

    it uses divide and conquer.
    there are three situations.
    the max is in the left half or right half or cross the mid.
    and then recursively find the max


  • 0
    C
    struct sumIndex{
        int low;
        int high;
        int sumValue;
    };
    
    
    class Solution {
        
    public:
        sumIndex findMaxCross(vector<int> changes, int low, int mid, int high){
            int leftSum= -std::numeric_limits<int>::max();
            int sum=0;
            int maxLeft;
            for(int i=mid; i>=low; i--){
                sum += changes[i];
                if (sum>leftSum){
                    leftSum=sum;
                    int maxLeft=i;
                }
            }
            int rightSum= -std::numeric_limits<int>::max();
            sum=0;
            int maxRight;
            for (int j=mid+1;j<=high;j++){
                sum +=changes[j];
                if (sum>rightSum){
                    rightSum=sum;
                    int maxRight=j;
                    
                }
            }
            sumIndex cross;
            cross.low=maxLeft;
            cross.high=maxRight;
            cross.sumValue=leftSum+rightSum;
            return cross;
            }
            
            
            
        sumIndex findMax(vector<int> changes, int low, int high){
            sumIndex result;
            sumIndex left, right, cross;
            if(low==high){
                result.low=low;
                result.high=high;
                result.sumValue=changes[low];
            }
            else{
                int mid =(low+high)/2;
                left= findMax(changes, low, mid);
                right=findMax(changes, mid+1, high);
                cross=findMaxCross(changes,low, mid, high);
                
                if (left.sumValue>right.sumValue && left.sumValue>cross.sumValue)
                    result=left;
                else if(right.sumValue>left.sumValue && right.sumValue>cross.sumValue)
                    result=right;
                else
                    result=cross;
            }
            
            return result;
        }
    
        int maxProfit(vector<int> &prices) {
            
            vector<int> changes;
            
            changes.push_back(0);
            for (int i=1; i<prices.size(); i++)
                changes.push_back(prices[i]-prices[i-1]);
            
            return findMax(changes, 0, changes.size()-1).sumValue;
            }
    };

  • 0
    P

    I'm sure your book doesn't say this is the most efficient way to find the answer


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.