主題
難度: 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
}
}
達人
