最大化股票交易的利潤

題目描述

實現一個算法尋找最大化股票交易利潤的策略。介紹如下：

• 股票價格每天都在變化，以數組的索引表示交易日，以數組的元素表示每天的股票價格。
• 可以通過買入和賣出獲得利潤。一天只能進行一次買入或賣出操作，一次買入加賣出操作稱為一次交易次數。
• 你只能交易一次，求使得利潤最大的交易策略。

輸入描述

第一行為數字?NN，表示共有?NN?天。

第二行為?NN?個數字?AiAi?，表示每天的股票價格。

其中，1≤N,Ai≤1041≤N,Ai?≤104。

輸出描述

輸出一行，為交易一次的最大利潤（有可能利潤為負）。

輸入輸出樣例

示例

輸入

8
2 5 6 1 4 3 1 3

輸出

4

運行限制

• 最大運行時間：1s
• 最大運行內存: 256M

總通過次數: 3836??|??總提交次數: 4156??|??通過率: 92.3%

難度: 中等???標簽: 動態規劃

最大化股票交易利潤的算法實現

問題分析

給定一個長度為?N?的股票價格數組，要求通過一次交易（即一次買入和一次賣出）獲得最大利潤。交易規則如下：

• 買入必須在賣出之前（即交易順序為?買入 → 賣出）
• 每天只能進行一次操作（買入或賣出）
• 利潤可能為負（即虧損情況需輸出負值）
• 若天數不足 2 天（無法完成交易），則利潤為 0

算法設計

使用??貪心算法??在?O(N)?時間內解決問題：

1. ??初始化??：
   • 記錄遍歷過程中的最小價格?min_price
   • 初始化最大利潤?max_profit?為極小值（如?INT_MIN）
2. ??遍歷價格數組??：
   • 對于第?i?天（i≥1）：
     • 計算當前賣出利潤：當前價格 - min_price
     • 更新最大利潤：max_profit = max(當前利潤, max_profit)
     • 更新最小價格：min_price = min(當前價格, min_price)
3. ??邊界處理??：
   • 若?N<2，直接返回 0（無法交易）

     #include <iostream>
     #include <vector>
     #include <climits>
     using namespace std;int main() {int n;cin >> n;vector<int> prices(n);for (int i = 0; i < n; i++) {cin >> prices[i];}// 處理無法交易的情況if (n < 2) {cout << 0 << endl;return 0;}int min_price = prices[0];int max_profit = INT_MIN;  // 初始化為最小整數for (int i = 1; i < n; i++) {// 計算當前賣出利潤int current_profit = prices[i] - min_price;// 更新最大利潤if (current_profit > max_profit) {max_profit = current_profit;}// 更新最小價格if (prices[i] < min_price) {min_price = prices[i];}}cout << max_profit << endl;return 0;
     }

     算法解析

   • ??時間復雜度??：O(N)，僅需一次遍歷數組
   • ??空間復雜度??：O(1)，僅使用常量額外空間
   • ??關鍵步驟??：
     • ??最小價格追蹤??：動態記錄歷史最低價，確保買入成本最低
     • ??利潤實時計算??：用當前價格與歷史最低價計算潛在利潤
     • ??負利潤處理??：不強制返回 0，允許輸出負值（虧損交易）

   • 示例驗證

   • ??輸入??：[2, 5, 6, 1, 4, 3, 1, 3]

     • ??執行過程??：

       天數	價格	最小價格	當前利潤	最大利潤
       1	2	2	-	INT_MIN
       2	5	2	3	3
       3	6	2	4	??4??
       4	1	1	-1	4
       5	4	1	3	4
       6	3	1	2	4
       7	1	1	0	4
       8	3	1	2	4

     • ??輸出??：4（第 1 天買入價 2，第 3 天賣出價 6）

   • ??虧損案例??：[5, 4, 3, 2, 1]

     • ??輸出??：-1（最小虧損為第 1 天買入價 5，第 2 天賣出價 4）

   • 算法優勢

   • ??高效性??：單次遍歷解決，避免?O(N2)?暴力枚舉
   • ??魯棒性??：正確處理正/負利潤及邊界條件
   • ??空間優化??：無需額外數據結構

   • 邊界情況測試

     輸入	輸出	說明
     [7]	0	單天無法交易
     [3, 1]	-2	強制交易虧損
     [1, 100]	99	最大利潤為正
     [2, 2, 2]	0	價格不變無利潤