【Leetcode 每日一題】121.買賣股票的最佳時機

題目描述

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

如果你最多隻允許完成一筆交易（即買入和賣出一支股票），設計一個算法來計算你所能擷取的最大利潤。

注意你不能在買入股票前賣出股票。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
     注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
           

示例 2:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
           

思路一——優化的暴力法

根據觀察，連續兩天的利潤若為負，肯定不購買；若為正，則連續購買到利潤為負，期間記錄利潤最大值。

根據這個思想，周遊數組每個元素，進行該計算，即可得出。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int Max=0;
        if(prices.empty())
            return Max;
        for(int i=0;i<prices.size()-1;i++)
        {
            if(prices[i+1] > prices[i])//利潤增長再計算
            {
                int j=i+1;
                int profit = prices[i+1] - prices[i];
                int tempMax = profit;
                while(profit>0 && j<prices.size()-1)
                {
                    profit += prices[j+1] - prices[j];
                    j++;
                    tempMax = max(tempMax,profit);
                }
                Max = max(tempMax,Max);
            }
        }
        return Max;
    }
};
           

思路二——一次周遊

周遊數組，依次記錄目前的最小值，若接下來的售出金額都高于該最小值，那麼計算利潤與最大利潤進行對比。Eg：[2,5,1,3]

public class Solution {
    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;
    }
}