開源地址：點擊該鏈接
題目描述
* https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
* 題目描述：
* 給定一個陣列，它的第 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，
解題思路
* 解題思路：
* 首先遍歷陣列是從左往右的，即先買入后賣出的順序
* 然后對每一個價格首先判斷是否是小于當前最小值
* 即判斷當前價格是否適合賣出，如果不小于，則適合賣出
* 然后檢查是否產生了最大效益
* 如果小于，即產生了新的最小值，則更新最小值即可
*
* 另一種解題思路：
* 詳情請參考：https://leetcode-cn.com/problems/
* best-time-to-buy-and-sell-stock/solution/
* 121-mai-mai-gu-piao-de-zui-jia-shi-ji-dp-7-xing-ji/
* 該方法的核心思想是
* 區間和可以轉換成求差的問題，求差問題，也可以轉換成區間和的問題
* 所以該問題就可以轉化為最大連續子區間和的問題
*
* 可能的疑問：
* 為什么當前的最小值一定比后邊的某個較小值和一個較大值
* 產生的利潤更大，這是因為如果某個較小值能和后邊的
* 一個較大值產生利潤，那么當前的最小值產生的利潤一定
* 比這個較小值更大
示例代碼
/* 第一種解題思路 */
class Solution_1 {
public:
int maxProfit(vector<int>& prices) {
int min = INT_MAX;
int max = 0;
for (int i=0; i<prices.size(); i++) {
if (min > prices[i])
min = prices[i];
else if (prices[i] - min > max)
max = prices[i] - min;
}
return max;
}
};
/* 問題轉化為最大連續子陣列的和 */
class Solution_2 {
public:
int maxProfit(vector<int>& prices) {
int min = INT_MAX;
int max = 0, sum = 0;
for (int i=1; i<prices.size(); i++) {
if (sum < 0) {
sum = prices[i] - prices[i-1];
} else {
sum += (prices[i] - prices[i-1]);
}
if (sum > max)
max = sum;
}
return max;
}
};
往期推薦
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6684.html
標籤：其他