2014.23.56

Say you have an array for which the ith 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:

　　To maximize the profit, you have to buy low and sell high, and profit from the margin.

　　Let f[n] be the maximum profit you can get by selling on the nth day, then f[n] = price[n] - min(price[0], price[1], ..., price[n - 1]);

　　There're two rules:

　　　　1. You would always buy at the lowest price possible.

　　　　2. You must buy before you sell something.

　　Just write down what you think with code. You can also think in a reversed manner. It would produce different code, but same outcome.

　　Time complexity is O(n), space complexity is O(1).

Accepted code:

1 class Solution { 2 public: 3     int maxProfit(vector
     
       &prices) { 4         // IMPORTANT: Please reset any member data you declared, as 5         // the same Solution instance will be reused for each test case. 6         int max_value; 7         int max_profit; 8          9         if(prices.size() <= 0){10             return 0;11         }12         13         int i, n;14         15         n = prices.size();16         for(i = n - 1; i >= 0; --i){17             if(i == n - 1){18                 max_value = prices[i];19                 max_profit = 0;20             }else{21                 if(prices[i] > max_value){22                     max_value = prices[i];23                 }24                 if(max_value - prices[i] > max_profit){25                     max_profit = max_value - prices[i];26                 }27             }28         }29         30         return max_profit;31     }32 };