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

リンク

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

概要

• 毎日の株価のデータpricesが与えられる
• 「買う」「売る」「なにもしない」のいずれかができるので、利益の最大化を目指す

解法

値が上がったら売り、下がったら売らない。

class Solution {
    public int maxProfit(int[] prices) {
        int total = 0;
        for(int i=1; i<prices.length; i++) {
            if(prices[i] > prices[i-1]) {
                total += prices[i] - prices[i-1];
            }
        }
        
        return total;
    }
}

折れ線グラフで考えるとわかりやすい。
以下は[7, 1, 5, 3, 6, 4]を折れ線グラフにしたもの。

このうち、右肩上がりの部分をすべて足したものが最大利益となる。

おわりに

図で考えれば一発だけど、理解するまでに結構かかった。
数学的な考え方が苦手なのかも。