[LeetCode] Best Time to Buy and Sell Stock Solution

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.

» Solve this problem

[Thoughts]
Scan from left to right. And keep track the minimal price in left. So, each step, only calculate the difference between current price and minimal price.
If this diff large than the current max difference, replace it.


[Code]

1:    int maxProfit(vector<int> &prices) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int minV=INT_MAX; int max =0;  
5:      int diff=0;  
6:      for(int i =0; i< prices.size(); i++)  
7:      {  
8:        if(prices[i]<minV) minV = prices[i];  
9:        diff = prices[i] - minV;  
10:        if(max<diff)  
11:          max = diff;  
12:      }  
13:      return max;  
14:    }