問題
Say you have an array for which the element is the price of a given stock on day .
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
自分の解答
public int maxProfit(int[] prices) { if (prices.length <= 1) { return 0; } int maxProfit = 0; for (int i = 0; i < prices.length - 1; i++) { for (int m = i + 1; m < prices.length; m++) { int profit = prices[m] - prices[i]; if (maxProfit < profit) { maxProfit = profit; } } } return maxProfit; }
コード理解
別解
public int maxProfit(int prices[]) { int minprice = Integer.MAX_VALUE; int maxprofit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minprice) minprice = prices[i]; else if (prices[i] - minprice > maxprofit) maxprofit = prices[i] - minprice; } return maxprofit; }
Time : / Space :
絶対を回避しなきゃいけないやつだって思ったけどできなかった。。。
ポイントは、新たな最小値を見つけたら、それまでのmaxProfit
以外の数値は破棄していいということか。それまでの最小値はもう捨ててよくて、そこから新しくまたmaxProfitを探せば良い。
min
とmaxProfit
変数がキーだということに気づきたい。max
を保持しておく必要がない。求めたいものが何かをよく考えれば気づける・・・のかなぁ。
コード見たらもちろん分かるんだけどな〜〜思いつかなかった。悔しい。
今後のための考え方
- 求めたいものが何か(何が最低限必要か)をよく考えてどれを変数にするかを決めればいいロジックが浮かぶかも
- 折れ線グラフにしてイメージすればロジック浮かぶかも