求解股票经纪人问题Java

股票经纪人问题是一道经典的贪心算法问题。以下是Java的实现：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class StockBroker {
    private static class Stock {
        int buyTime; // 买入时间
        int sellTime; // 卖出时间
        int profit; // 利润

        Stock(int buy, int sell, int profit) {
            this.buyTime = buy;
            this.sellTime = sell;
            this.profit = profit;
        }
    }

    public static List<Stock> getBestStocks(int[] prices) {
        List<Stock> stocks = new ArrayList<>();
        int n = prices.length;

        // 找出所有买卖时机和利润
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int profit = prices[j] - prices[i];
                stocks.add(new Stock(i, j, profit));
            }
        }

        // 按照利润从大到小排序
        Collections.sort(stocks, Comparator.comparingInt(s -> -s.profit));

        // 找出不重叠的买卖时机
        List<Stock> result = new ArrayList<>();
        boolean[] used = new boolean[n];
        for (Stock stock : stocks) {
            boolean overlap = false;
            for (int i = stock.buyTime; i <= stock.sellTime; i++) {
                if (used[i]) {
                    overlap = true;
                    break;
                }
            }
            if (!overlap) {
                for (int i = stock.buyTime; i <= stock.sellTime; i++) {
                    used[i] = true;
                }
                result.add(stock);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] prices = {2, 5, 3, 7, 1, 4, 9, 6};
        List<Stock> result = getBestStocks(prices);
        for (Stock stock : result) {
            System.out.printf("Buy at %d, sell at %d, profit %d%n", stock.buyTime, stock.sellTime, stock.profit);
        }
    }
}

在这个实现中，我们首先找出所有可能的买卖时机和利润，并按照利润从大到小排序。然后，我们从利润最大的股票开始，依次检查它的买卖时机是否与之前选择的股票重叠。如果没有重叠，则选择该股票，并标记其买卖时机上的天数为已使用，以便下次检查。最终我们得到的所有股票即为最佳的选择。

注意：此实现的时间复杂度为 $O(n^3)$，在实际问题中可能不太适用。可以使用更高效的算法来解决股票经纪人问题。