arrays - 最高利润股票市场算法

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
对于最大利润的股票市场问题（使用O（nLogn）方法或O（n）方法），而不是在最大利润的数组A中返回对，如何返回数组A中的每一天的最大利润的数组？
最大利润可以定义为在第一天买入，在第二天卖出。

最佳答案

你可以用O(n)复杂性来做到这一点。只是一个从左到右的传球。溶液取自here。

public int getMaxProfit(int[] stockPricesYesterday) {

    // make sure we have at least 2 prices
    if (stockPricesYesterday.length < 2) {
        throw new IllegalArgumentException("Getting a profit requires at least 2 prices");
    }

    // we'll greedily update minPrice and maxProfit, so we initialize
    // them to the first price and the first possible profit
    int minPrice = stockPricesYesterday[0];
    int maxProfit = stockPricesYesterday[1] - stockPricesYesterday[0];

    // start at the second (index 1) time
    // we can't sell at the first time, since we must buy first,
    // and we can't buy and sell at the same time!
    // if we started at index 0, we'd try to buy /and/ sell at time 0.
    // this would give a profit of 0, which is a problem if our
    // maxProfit is supposed to be /negative/--we'd return 0!
    for (int i = 1; i < stockPricesYesterday.length; i++) {
        int currentPrice = stockPricesYesterday[i];

        // see what our profit would be if we bought at the
        // min price and sold at the current price
        int potentialProfit = currentPrice - minPrice;

        // update maxProfit if we can do better
        maxProfit = Math.max(maxProfit, potentialProfit);

        // update minPrice so it's always
        // the lowest price we've seen so far
        minPrice = Math.min(minPrice, currentPrice);
    }

    return maxProfit;
}

其他一些变体here和here。
基本上，如果您对编写算法有疑问，我建议您首先在GeekforGeeks查看，这是一个很好的门户。