LeetCoding Challenge Oct. 18: Best Time to Buy and Sell...

LeetCode October Challenge の 18 日目。

今日の問題は Best Time to Buy and Sell Stock IV。

問題の概要

• 一日ごとの株価の動きを表した配列が与えられるので、取引回数 (株の購入・売却をセットにして１回と数える)を最大 k 回までと制限した上で利益を最大化する

考え方

• 問題のタイトルにあるとおり、シリーズになっている問題ですね 💰
• 前回取り組んだやつではステートマシンを使った気がするので、今回もステートマシンを使えば解けるかな…
  • k 個の購入状態 と k 個の売却状態が存在する
  • 図にすると以下の通り (k = 2 の場合)
  • 
  • 計算量が O(n * k) になってスマートな感じがしないんだけど、どうだろ？
• あれ、でも k って最大で $10^9$ になると書いてあるぞ… 😨
  • 値動きの配列は最大で $10^4$ なので、取引回数は最大でも prices.length / 2 回しか行えないのか
  • であれば、k >= prices.length / 2 となる場合は状態が 2 つのステートマシンで解けるね 😅
• そんなこんなでひとまず実装 → submit → 何度か wrong answer → accept 🎉
  • Runtime: 3 ms だけど、 Your runtime beats 61.06 % of java submissions. ということでなかなか厳しい結果だ…
• Runtime 上位陣の実装を観察してみよう
  • アプローチは僕が submit したのと概ね同じようだ
  • でも、k >= prices.length / 2 のときのアルゴリズムが随分と異なっているね
    • 
    • 「えー本当にこれで正しい解が求まるの…？？」と思ってしまうんだけど、よくよく考えてみると「まあ、確かにそれっぽい解は求まりそう 🤔」という気分になる
• しかし、根本的なアルゴリズムはほとんど差がないのに runtime で差が出るのはちょっとおかしい…
  • まさかとは思うが、メソッド抽出しているのをやめてインライン化したら速くなるとかかな
• メソッドを手動インライン化して submit → runtime は 2ms ニナッタヨ 🤦‍♂️
  • Your runtime beats 97.31 % of java submissions. ということで、まあこれでいいかな…

コード

メソッドインライン化前

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length <= 1 || k == 0) {
            return 0;
        }

        if (k >= prices.length / 2) {
            return maxProfitWithoutLimit(k, prices);
        } else {
            return maxProfitWithLimit(k, prices);
        }
    }

    int maxProfitWithoutLimit(int k, int[] prices) {
        int buyState = -prices[0];
        int sellState = 0;

        for (int i = 1; i < prices.length; i++) {
            int newBuyState = Math.max(buyState, sellState - prices[i]);
            sellState = Math.max(sellState, buyState + prices[i]);
            buyState = newBuyState;
        }

        return sellState;
    }

    int maxProfitWithLimit(int k, int[] prices) {
        int[] buyStates = new int[k];
        int[] sellStates = new int[k];

        Arrays.fill(buyStates, Integer.MIN_VALUE);

        buyStates[0] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i];
            sellStates[0] = Math.max(sellStates[0], buyStates[0] + price);
            buyStates[0] = Math.max(buyStates[0], -price);

            for (int j = 1; j < k; j++) {
                sellStates[j] = Math.max(sellStates[j], buyStates[j] + price);
                buyStates[j] = Math.max(buyStates[j], sellStates[j - 1] - price);
            }
        }

        return sellStates[k - 1];
    }
}

メソッドインライン化後

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length <= 1 || k == 0) {
            return 0;
        }

        if (k >= prices.length / 2) {
            int buyState = -prices[0];
            int sellState = 0;

            for (int i = 1; i < prices.length; i++) {
                int newBuyState = Math.max(buyState, sellState - prices[i]);
                sellState = Math.max(sellState, buyState + prices[i]);
                buyState = newBuyState;
            }

            return sellState;

        } else {
            int[] buyStates = new int[k];
            int[] sellStates = new int[k];

            Arrays.fill(buyStates, Integer.MIN_VALUE);

            buyStates[0] = -prices[0];

            for (int i = 1; i < prices.length; i++) {
                int price = prices[i];
                sellStates[0] = Math.max(sellStates[0], buyStates[0] + price);
                buyStates[0] = Math.max(buyStates[0], -price);

                for (int j = 1; j < k; j++) {
                    sellStates[j] = Math.max(sellStates[j], buyStates[j] + price);
                    buyStates[j] = Math.max(buyStates[j], sellStates[j - 1] - price);
                }
            }

            return sellStates[k - 1];
        }
    }
}