LEET code -- 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.

Subscribe to see which companies asked this question

智障方法
兩個for 去找最大值
但是會超過時間限制

1 2 3 4 5 6 7 8 9 10 11 12

int maxProfit(int* prices, int pricesSize) { int size=pricesSize; int max=0; for(int i =0;i<size;i++){ for(int j =i;j<size;j++){ if( prices[j] - prices[i] > max ){ max = prices[j] - prices[i]; } } } return max; }

---------------
事實上把它當作訊號來看
就是找絕對低峰跟絕對高峰

用兩個指標 一個是買的價錢與天數  一個是賣的價錢與天數
不斷去找有沒有最低價前跟最高價錢     拿後要注意賣的天數要比買的高
還有當設定買的時候，賣也要設定，因為買一改  以前的賣就不行了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int maxProfit(int* prices, int pricesSize) { if(prices==NULL || pricesSize<2)return 0; int size=pricesSize; int max=0,buydate=0,selldate=1,buy=prices[0],sell=prices[1]; for(int i =1;i<size;i++){ if(prices[i] > sell){ sell = prices[i]; selldate=i; } if(prices[i] < buy){ buy = prices[i]; buydate = i; sell = prices[i]; selldate=i; } if ( selldate > buydate){ max = (max>(sell-buy))? max:(sell-buy); } } return max; }