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

最大化股票交易的利润

题目描述

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

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

输入描述

第一行为数字 NN，表示共有 NN 天。

第二行为 NN 个数字 AiAi，表示每天的股票价格。

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

输出描述

输出一行，为交易一次的最大利润（有可能利润为负）。

输入输出样例

示例

输入

8
2 5 6 1 4 3 1 3

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

总通过次数: 3836 | 总提交次数: 4156 | 通过率: 92.3%

难度: 中等标签: 动态规划

最大化股票交易利润的算法实现

问题分析

给定一个长度为 N 的股票价格数组，要求通过一次交易（即一次买入和一次卖出）获得最大利润。交易规则如下：

买入必须在卖出之前（即交易顺序为 买入 → 卖出）
每天只能进行一次操作（买入或卖出）
利润可能为负（即亏损情况需输出负值）
若天数不足 2 天（无法完成交易），则利润为 0

算法设计

使用贪心算法在 O(N) 时间内解决问题：

初始化：
- 记录遍历过程中的最小价格 min_price
- 初始化最大利润 max_profit 为极小值（如 INT_MIN）
遍历价格数组：
- 对于第 i 天（i≥1）：
  - 计算当前卖出利润：当前价格 - min_price
  - 更新最大利润：max_profit = max(当前利润, max_profit)
  - 更新最小价格：min_price = min(当前价格, min_price)
边界处理：
- 若 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 价格不变无利润