[蓝桥杯]最大化股票交易的利润

最大化股票交易的利润

题目描述

实现一个算法寻找最大化股票交易利润的策略。介绍如下：

• 股票价格每天都在变化，以数组的索引表示交易日，以数组的元素表示每天的股票价格。
• 可以通过买入和卖出获得利润。一天只能进行一次买入或卖出操作，一次买入加卖出操作称为一次交易次数。
• 你只能交易一次，求使得利润最大的交易策略。

输入描述

第一行为数字 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	价格不变无利润