主題

[LeetCode C#] 121. Best Time to Buy and Sell Stock - Dynamic Programming, Maximum Subarray

帥氣跳蚤蛋 | 2021-07-28 00:30:07 | 巴幣 0 | 人氣 102

難度: Easy
===========================================================================
給予一組由價格組成的陣列"prices",其中prices[i]表示股票在第i天的價格,
您需要在某天買進,並在未來的某天賣出股票,來最大化利潤

返回在本次交易中可獲得的最大利潤,若無法獲利則返回0
===========================================================================
條件限制:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
===========================================================================
測資1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
注意!不允許在第2天買入,然後在第1天賣出,因為必須先買入在賣出

測資2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
===========================================================================
本題有2種可行解法,
第1種解法就遍歷1次陣列
第2種解法,將問題改為每天的價差,並計算在某段時間的最大獲利,可採用與Leetcode 53相同的解法

解法1-1:
遍歷每天的價格,
取得目前為止的最低價格,
當天收益=當天的價格-目前為止的最低價格,
再比較目前為止的最大收益與當天收益,來取得最大的收益

public class Solution
{
    public int MaxProfit(int[] prices)
    {
        int min_price = prices[0];  //先預設第1天為最低價格
        int max_profit = 0; //最大收益為0
        for(int i=1;i<prices.Length;i++)//由第2天開始比較每天收益
        {
            min_price = Math.Min(min_price, prices[i]); //取得當前的最低價格
            max_profit = Math.Max(max_profit, prices[i] - min_price);   //當前的最大利潤
        }
        return max_profit;
    }
}
-----------------------------------------------------------------------------------------------------------------------------------
解法1-2:
與解法1-1相同,只讓其解法符合Dynamic Programming

public class Solution
{
    public int MaxProfit(int[] prices)
    {
        int[] min_price = new int[prices.Length];
        int[] max_profit = new int[prices.Length];
        min_price[0] = prices[0];   //先預設第1天為最低價格
        max_profit[0] = 0;  //最大收益為0
        for (int i=1;i<prices.Length;i++)   //由第2天開始比較每天收益
        {
            min_price[i] = Math.Min(min_price[i-1], prices[i]); //由第1天到前1天為止的最低價格,與當天的最低價格比較,取得當前的最低價格
            max_profit[i] = Math.Max(max_profit[i - 1], prices[i] - min_price[i - 1]);  //由第1天到前1天為止的最高利潤,與當天的利潤比較,取得當前的最大利潤
        }
        return Enumerable.Max(max_profit);  //遍歷每天的利潤,找出最大值

    }
}
-----------------------------------------------------------------------------------------------------------------------------------
解法2:
首先計算每天的價差,
再由每天的價差中,找尋某段時間的最大收益,等同於找尋最大子數組的問題

public class Solution
{
    public int MaxProfit(int[] prices)
    {
        if (prices.Length <= 1) //若只有1筆價格則返回0
            return 0;

        int[] diff_price = new int[prices.Length - 1];//每天的價差
        for(int i=1;i<prices.Length;i++)    //計算每天的價差
            diff_price[i - 1] = prices[i] - prices[i - 1];

        return MaxSubArray(diff_price); //由每天的價差,找出在這段時間裡最大的收益
    }

    public int MaxSubArray(int[] nums)  //Maximum Subarray Problem,與Leet code 35的解法差不多
    {
        int max_current = 0;    //(35題為從nums[0])
        int max_result = 0; //避免產生負收益(35題為從nums[0])
        for (int i = 0; i < nums.Length; i++)   //從第1天開始計算(35題為從nums[1]開始計算)
        {
            max_current = Math.Max(nums[i], nums[i] + max_current); //取得今天的最大的價差
            max_result = Math.Max(max_current, max_result); //取得目前為止最大的價差
        }
        return max_result;  //返回最大的收益,若負收益則反為0
    }
}

創作回應

相關創作

更多創作