122. 買賣股票的最佳時機 II

題目

給你一個整數數組 prices ，其中 prices[i] 表示某支股票(piao)第 i 天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次買(mai)賣該股票，但要確保你持(chi)有的股票不超過(guo)一股。

返(fan)回(hui) 你能(neng)獲得(de)的 最大 利潤 。

例子

輸入：prices = [7,1,5,3,6,4]

輸出：7

解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4。
隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3。
最(zui)大總利潤(run)為 4 + 3 = 7

解法一

1. 若價格一直往下跌，不買入
2. 假設第一天買入，若買入后價格往下跌，應該下一天買入
3. 若下一天價格往下跌，應該當天賣出
4. 若到最后一天，應該清盤，若之前買入賣出，否則維持現狀

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1)
        return 0;

    int maxProfit = 0, minPrice = prices[0];
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] < minPrice) {          // 若價格比之前低，應該買入
            minPrice = prices[i];
        } else if (i == prices.length - 1) { // 最后一天，強制清盤
            if (prices[i] - minPrice > 0) {
                maxProfit += (prices[i] - minPrice);
            }
        } else if (prices[i + 1] < prices[i]) { // 若后一天價格比當前低&&之前已經買入，就應該當天賣出
            maxProfit += (prices[i] - minPrice);
            minPrice = prices[i + 1];
        }

        System.out.println(
                String.join(",", String.valueOf(prices[i]), String.valueOf(minPrice), String.valueOf(maxProfit)));
    }
    return maxProfit;
}

解法二

貪心算法，若當天價格比(bi)前一天高，即可賣出，獲(huo)取利潤，統計(ji)結果利潤

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1)
        return 0;

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