輸入：一個數組prices,prices[i]表示第i天股票的價格。
輸出：買賣股票的最大收益。
規則：只允許最多買一次，最多賣一次股票。如果覺得價格不合適，可以不買賣。
分析1：最先想到的是暴力搜索，每天都可以買或者賣，當然要符合規則。倒是AC了，但是時間太長。這個復雜度應該是2^n。

private int maxProfit;public int maxProfit(int[] prices) {maxProfit = 0;trasaction(prices,0,false,true,0);return maxProfit;}private void trasaction(int[] prices,int idx,boolean sell,boolean buy,int profit){if(idx==prices.length){maxProfit = Math.max(maxProfit,profit);}else{if(buy){trasaction(prices,idx+1,true,false,profit-prices[idx]);}else if(sell){maxProfit = Math.max(maxProfit,profit+prices[idx]);}trasaction(prices,idx+1,sell,buy,profit);}}

分析2：這是參考別的答案。只要找到最低成本minPrice，如果其下標為i，只要j>i，prices[j]-minPrice就是收益。各個收益取最大值。這是技巧問題，背多次，形成這樣的思維。

public int maxProfit(int[] prices) {int maxProfit = 0;int minPrice = Integer.MAX_VALUE;for(int i=0;i<prices.length;i++){minPrice = Math.min(minPrice,prices[i]);maxProfit = Math.max(maxProfit,prices[i]-minPrice);}return maxProfit;}

進階題目122：可以多次買賣股票。但是得先買股票才能賣股票。如果已經買了股票，需要賣了，才能再買。
分析1：暴力購買。超時。
學習1：參考網頁。收益profit是子收益sub-profit的和。在第i天購買，第j天賣，每個sub-profit是不同的。在[i,j]范圍內我們該怎么選擇才能讓sub-profit最大呢？我們應該找到的j是在這個范圍內prices[j]是盡可能大的那個值，i是在這個范圍內prices[i]盡可能小的那個值。
　舉例來說。我們有數組[3,2,5]。我們會選擇[2,5],而不會選擇[3,5]，因為2<5。
　如果數組[3,2,5,8]，我們會選擇[2,8]，因為5<8。
　從這兩個例子，我們觀察到我們選擇購買的那個x應該是一個連續值中的最小值。我們賣出去的那個y應該一個連續序列中的最大值。
　再舉個例子。[3,2,5,8,1,9]，雖然1是最小值，但是我們選擇2，因為2是一個連續遞減序列的最小值（從3開始）。同樣雖然9是最大值，但是我們選擇8。因為8是從2開始的連續遞增序列的最大值。
　實際上，[3,2,5,8,1,9]被分成了2個子數組，分別選擇[2,8]和[1,9]。

public int maxProfitV2(int[] prices) {int maxProfit = 0;int i=0;int n = prices.length;while(i<n-1){while(i<n-1 && prices[i+1]<=prices[i]) i++;int buy = prices[i];while(i<n-1 && prices[i+1]>prices[i]) i++;int sell = prices[i];maxProfit += sell - buy;}return maxProfit;}

總結

以上是生活随笔為你收集整理的121 Best Time to Buy and Sell Stock的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。