递归过程中维护日期索引：股票买卖最佳交易日定位问题

Got it, let's work through this problem together. The key pain point here is that your current recursive logic only tracks the maximum profit, but you're losing the corresponding buy/sell day indices—and you want to avoid static variables (great call, static state is a recipe for messy, hard-to-debug code).

The cleanest way to fix this without static variables is to package your profit and index data together in a helper class, then have your recursive private method return this class instead of just an integer. This way, every step of the recursion carries both the profit value and the associated day indices, so nothing gets lost.

具体实现方案 #

First, create a private inner helper class to encapsulate the trade details: it'll hold the maximum profit, buy index, and sell index. Then rewrite your recursive logic to return instances of this class, and use a public method to expose the results to callers.

Here's the modified version of your Stock class with this approach:

public class Stock {

    // 私有辅助类：封装最大收益和对应的买卖日索引
    private static class TradeResult {
        int maxProfit;
        int buyIndex;
        int sellIndex;

        TradeResult(int maxProfit, int buyIndex, int sellIndex) {
            this.maxProfit = maxProfit;
            this.buyIndex = buyIndex;
            this.sellIndex = sellIndex;
        }
    }

    // 对外公开的方法：返回最大收益，同时可获取买卖日期索引
    public static int getMaximumProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0; // 不足两天无法交易
        }
        TradeResult bestTrade = findBestTradeRecursive(prices, 0, prices.length - 1);
        // 这里可以根据需求返回索引或者直接打印
        System.out.printf("最佳买入日索引：%d，最佳卖出日索引：%d，收益：%d%n", 
                          bestTrade.buyIndex, bestTrade.sellIndex, bestTrade.maxProfit);
        return bestTrade.maxProfit;
    }

    // 私有递归方法：处理指定区间的最佳交易，返回完整的TradeResult
    private static TradeResult findBestTradeRecursive(int[] prices, int start, int end) {
        // 基准情况：区间长度不足2，无法交易
        if (start >= end) {
            return new TradeResult(0, -1, -1);
        }

        int mid = (start + end) / 2;
        // 递归处理左右两个子区间
        TradeResult leftBest = findBestTradeRecursive(prices, start, mid);
        TradeResult rightBest = findBestTradeRecursive(prices, mid + 1, end);
        
        // 计算跨区间的最佳交易：左半区找最低价（买入），右半区找最高价（卖出）
        int minBuyIndex = start;
        for (int i = start; i <= mid; i++) {
            if (prices[i] < prices[minBuyIndex]) {
                minBuyIndex = i;
            }
        }
        int maxSellIndex = mid + 1;
        for (int i = mid + 1; i <= end; i++) {
            if (prices[i] > prices[maxSellIndex]) {
                maxSellIndex = i;
            }
        }
        int crossProfit = prices[maxSellIndex] - prices[minBuyIndex];
        TradeResult crossBest = new TradeResult(crossProfit, minBuyIndex, maxSellIndex);

        // 比较三种情况的收益，返回最优结果
        if (leftBest.maxProfit >= rightBest.maxProfit && leftBest.maxProfit >= crossProfit) {
            return leftBest;
        } else if (rightBest.maxProfit >= leftBest.maxProfit && rightBest.maxProfit >= crossProfit) {
            return rightBest;
        } else {
            return crossBest;
        }
    }

    // 测试示例
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        getMaximumProfit(prices); // 输出：最佳买入日索引：1，最佳卖出日索引：4，收益：5
    }
}

为什么这个方案有效？ #

• 无静态变量: 所有状态（收益+索引）都通过方法参数和返回值传递，代码线程安全且无副作用。
• 封装性: 私有递归方法负责处理分治逻辑的细节，公开方法给调用者提供简洁的接口。
• 数据完整性: 通过TradeResult把收益和索引绑定在一起，递归过程中不会丢失收益与对应交易日的关联关系。

内容的提问来源于stack exchange，提问作者Pantelis