[leetCode] Top Interview 150: Best Time to Buy and Sell Stock

「まいにちleetCode」って言ってたのに一カ月ぐらい休んでた。

概要

• 各日の株の値段を格納した配列 prices が渡される
• 株を売買したときの 利益の最大値 を求める
  • （もちろん）過去に遡って売ることはできない

解法

先にダメなほうの解法。

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int i=0; i<prices.length-1; i++) {
            for(int j=i+1; j<prices.length; j++) {
                if(i == j) continue;
                max = Math.max(max, prices[j] - prices[i]);
            }
        }

        return max;
    }
}

すべてのパターンを一通り試して、最も高い差額を求めている。
計算量が $O(n^2)$ なので、そりゃTLEになる。

次に、通った時のコードがコレ。

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = prices[0];

        for (int i=1; i<prices.length; i++) {
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            minPrice = Math.min(minPrice, prices[i]);
        }

        return maxProfit;
    }
}

株が最も安い日 minPrice を更新しつつ、利益の最大値 maxProfit を求めている。

前提として、 maxPrice - minPrice が解となるとは限らない。たとえば[2, 4, 1]とかの場合、最大値と最小値はそれぞれ4, 1になるが、その通りに売る場合、 3日目から2日目に遡って売ることになってしまう。 今回はタイムマシーンがある可能性は勘案しないので、これは誤答。

これを前提として、一回のループで最大利益を割り出す方法を考える。
考え方としては、

1. i+1日目に売ると仮定する
2. 利益の最大値は、i+1日目より前の最小値の日に買ったときになる

という感じ。

参考

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150