华为OD机试 - 最大利润（Java 2024 E卷 100分）

在华为的OD机试中，最大利润问题是一个经典的动态规划问题，通常涉及到对利润的计算和优化，主要用于股票交易、资源分配等场景。我们接下来将通过问题的描述和动态规划的算法来解决这一问题，并给出Java代码示例。

问题描述

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你可以选择在某一天买入股票，并在未来的某一天卖出，要求买入的股票价格必须低于卖出的股票价格，目标是在遵循这些条件的情况下，获得最大利润。

动态规划思路

1. 状态定义：定义 maxProfit[i] 表示第 i 天的最大利润。
2. 状态转移：

3. 对于每一天 i，我们可以选择在这一天卖出，遍历之前的每一天 j（0 <= j < i），计算在第 j 天买入并在第 i 天卖出所能获得的利润： [ \text{maxProfit}[i] = \max(\text{maxProfit}[i], \text{prices}[i] - \text{prices}[j]) ]

4. 也可以直接使用前一日的最大利润来决定今天的最大利润，简化计算。

5. 结果求解：最终的结果即为 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）
    }
}

代码分析

1. 时间复杂度：O(n)，其中 n 是 prices 数组的长度。我们只需遍历一次数组。
2. 空间复杂度：O(1)，只使用了常量空间。

在上述代码中，我们通过维护一个 minPrice 变量来跟踪当前最小的买入价格，并在每次循环中计算卖出时的利润。这个实现能够有效地得到最大利润，并且清晰易懂，适合在机试中快速实现。

总结

最大利润问题是动态规划中的基础问题之一，掌握其解法对于许多实际问题的解决都有示范意义。在实际编程面试中，这类问题不仅考察编码能力，更考察思维的缜密性和问题的理解能力。通过动态规划，我们能够有效地简化问题，找到最优解。希望通过本文的阐述和代码示例，能帮助到更多正在准备华为机试的同学们。