Day 23, 121, Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock
Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
-------------------------------------------------
 Solution #1 O(n^2) straight forward iteration.

class Solution {
public:

    void profit (vector<int> &prices, vector<int> &prf, int index) {
        int cur = prices[index];
        int max = 0;
        for (int i=index+1;i<prices.size();i++) {
            int dif = prices[i] - cur;
            if (dif > max) {
                max = dif;
            }
        }
        prf[index] = max;
        if (index + 1 < prices.size())
            profit(prices,prf,index+1);
        
    }
    
    int findMax (vector<int> &prf) {
        int max = 0;
        for (int i=0;i<prf.size();i++) {
            if (prf[i]>max) max = prf[i]; 
        }
        return max;
    }

    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (prices.size() == 0) return 0;
        vector<int> prf(prices.size());
        profit(prices,prf,0);
        return findMax(prf);
    }
};

Solution #2 O(n)
Note: tracking the index of minimum value

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int buy=0,sell=0;
        int min=0;
        int maxDif = 0;
        for (int i=0;i<prices.size();i++) {
            if (prices[min] > prices[i]) {
                min = i;    
            }
            int dif = prices[i] - prices[min];
            if (dif > maxDif) {
                buy = min;
                sell = i;
                maxDif = dif; 
            } 
        }
        return maxDif;
    }
};

Solution #3  O(n) space and efficiency
 DP: max = prices[i] - prices[i-1] + prices[i-1] - prices[i-2] + .... + prices[j+1] - prices[j] = prices[i]- prices[j]

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = prices.size();
        if (size < 2) {
            return 0;
        }
        int max = 0;
        int curMax = 0;
        for (int i=1;i<size;i++) {
            if (curMax > 0) {
                curMax += prices[i] - prices[i-1];
            }else {
                curMax = prices[i] - prices[i-1];
            }
            if (curMax > max) {
                max = curMax;
            }
        }
        return max;
    }
};

Update - 1, Dec 27th 2013
Solution #4, a much easier DP approach 
dp[i] represents the maximum profit among all prices, starting at index 0 to i. Hence dp[prices.size() - 1] has the max value we are looking for.

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) return 0;
        vector<int> dp(prices.size(),0);
        int minimum = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i] = max(dp[i - 1], prices[i] - minimum);
            minimum = mim(prices[i],minimum);
        }
        return dp[prices.size() - 1];
    }
};

Update - 2, Mar 29th 2014
Optimized space of Solution #4

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int size = prices.size();
        if (size == 0) {
            return 0;
        }    
        
        int minimum = prices[0];
        int maxP = 0;
        for (int i = 0; i < size; i++) {
            maxP = max (maxP, prices[i] - minimum);
            minimum = min(minimum,prices[i]);
        }
        
        return maxP;
    }
};

Solution #5, similar to #4. DP. thanks to Lan Xu
dp[i] has the highest price from dp[i + 1] to end

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int size = prices.size();
        if (size == 0) {
            return 0;
        }    
        
        vector<int> dp(size,0);
        for (int i = size - 2; i >= 0; i--) {
            dp[i] = max(dp[i + 1], prices[i + 1]);
        }
        
        int maxP = 0;
        for (int i = 0; i < size; i++) {
            maxP = max(maxP, dp[i] - prices[i]);
        }
        
        return maxP;
    }
};

Optimized space

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int size = prices.size();
        if (size == 0) {
            return 0;
        }    
        
        int maxP = 0;
        int highest = prices[size - 1]; // highest value from i to end
        for (int i = size - 2; i >= 0; i--) {
            maxP = max(maxP, highest - prices[i]);
            highest = max(highest, prices[i]);
        }
  
        return maxP;
    }
};