在华为的OD机试中，最大利润问题是一个经典的动态规划问题，通常涉及到对利润的计算和优化，主要用于股票交易、资源分配等场景。我们接下来将通过问题的描述和动态规划的算法来解决这一问题，并给出Java代码示例。
问题描述
给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你可以选择在某一天买入股票，并在未来的某一天卖出，要求买入的股票价格必须低于卖出的股票价格，目标是在遵循这些条件的情况下，获得最大利润。
动态规划思路
- 状态定义：定义
maxProfit[i]表示第i天的最大利润。 - 状态转移：
-
对于每一天
i，我们可以选择在这一天卖出，遍历之前的每一天j（0 <= j < i），计算在第j天买入并在第i天卖出所能获得的利润： [ \text{maxProfit}[i] = \max(\text{maxProfit}[i], \text{prices}[i] - \text{prices}[j]) ] -
也可以直接使用前一日的最大利润来决定今天的最大利润，简化计算。
-
结果求解：最终的结果即为
maxProfit数组的最大值。
Java代码示例
以下是一个 Java 实现最大利润的例子：
public class MaxProfit {
public static int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int maxProfit = 0;
int minPrice = prices[0]; // 初始化最小价格为第一天的价格
for (int i = 1; i < prices.length; i++) {
// 更新最小价格
if (prices[i] < minPrice) {
minPrice = prices[i];
}
// 计算当前利润
int profit = prices[i] - minPrice;
// 更新最大利润
if (profit > maxProfit) {
maxProfit = profit;
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
int result = maxProfit(prices);
System.out.println("最大利润是: " + result); // 输出应该是5，因为在第2天买入（价格为1）在第5天卖出（价格为6）
}
}
代码分析
- 时间复杂度：O(n)，其中 n 是
prices数组的长度。我们只需遍历一次数组。 - 空间复杂度：O(1)，只使用了常量空间。
在上述代码中，我们通过维护一个 minPrice 变量来跟踪当前最小的买入价格，并在每次循环中计算卖出时的利润。这个实现能够有效地得到最大利润，并且清晰易懂，适合在机试中快速实现。
总结
最大利润问题是动态规划中的基础问题之一，掌握其解法对于许多实际问题的解决都有示范意义。在实际编程面试中，这类问题不仅考察编码能力，更考察思维的缜密性和问题的理解能力。通过动态规划，我们能够有效地简化问题，找到最优解。希望通过本文的阐述和代码示例，能帮助到更多正在准备华为机试的同学们。
