01、題目分析
給定一個陣列 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格，你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票，設計一個演算法來計算你所能獲取的最大利潤，如果你不能獲取任何利潤，回傳 0 ，【leetcode】
示例1
輸入: [8,9,2,5,4,7,1]
輸出: 5
解釋：在第3天(股票價格 = 2)的時候買入，在第6天(股票價格 = 7)的時候賣出，最大利潤 = 7-2 = 5 ，不能選擇在第2天買入，第3天賣出，這樣就虧損7了；同時，你也不能在買入前賣出股票，
02、題解分析
方法1
分別計算不同時間買入和賣出的利潤，然后不斷更新，結束時就能找到利潤的最大值
方法2
采用動態規劃的方法【參考《團滅 LeetCode 股票買賣問題》】
對于動態規劃方法，我們具體到每一天，看看總共有幾種可能的「狀態」，再找出每個「狀態」對應的「選擇」，我們要窮舉所有「狀態」，窮舉的目的是根據對應的「選擇」更新狀態，
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
解釋：今天我沒有股票，有兩種可能：
要么是我昨天就沒有，然后今天選擇無操作，所以我今天還是沒有持有 【dp[i-1][0]】
要么是我昨天持有股票，但是今天我賣出了，所以我今天沒有持有股票了 【dp[i-1][1] + prices[i]】
dp[i][1] = max(dp[i-1][1], -prices[i]);
解釋：今天我持有股票，有兩種可能：
要么我昨天就持有著股票，然后今天選擇無操作，所以我今天還持有著股票 【dp[i-1][1]】
要么我昨天本沒有持有，今天買入股票 【-prices[i]】
由遞推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出其基礎都是要從dp[0][0]和dp[0][1]推匯出來，
那么dp[0][0]表示第0天沒有股票，不持有股票那么現金就是0，所以dp[0][0] = 0;
dp[0][1]表示第0天不持有股票，此時的持有股票就一定是買入股票了，因為不可能有前一天推出來，所以dp[0][0] -= prices[0];
方法3
因為股票就買賣一次，那么貪心的想法很自然就是取最左最小值，然后依次用右邊的值減去最小值，然后更新結果【參考代碼隨想錄】
03、題解
方法1
// 方法1
int maxProfit(int prices[],int len)
{
if (len < 2) {
return 0 ;
}
int ans=0;
for(int i=0; i<len; i++) {
for(int j=i+1; j<len; j++) {
ans = max(ans, prices[j] - prices[i]);
}
}
return max(0, ans);
}
方法2
// 方法2
int maxProfit5(int prices[],int len)
{
if (len < 2) {
return 0 ;
}
int dp[len][2]= {0};
dp[0][0]=0;
dp[0][1]=-prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], -prices[i]);
}
return dp[len - 1][0];
}
方法3
//方法3
int maxProfit5(int prices[],int len)
{
if (len < 2) {
return 0 ;
}
int low = 10000;
int result = 0;
for (int i = 0; i < len; i++) {
low = min(low, prices[i]); // 更新左邊最小價格
result = max(result, prices[i] - low); // 更新最大區間利潤
}
return result;
}
04、測驗結果
int len = 7;
int prices[len]= {8,9,2,5,4,7,1};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/500575.html
標籤：C
上一篇：一、HELLO,C++
下一篇：IOS OpenGL ES GPUImage 影像普瑞維特(Prewitt)邊緣檢測 GPUImagePrewittEdgeDetectionFilter