121. Best Time To Buy And Sell Stocks

给出若干天的股价,如果只有一次买入和卖出的机会,求最大利润
如果六天的股价为[7, 1, 5, 3, 6, 4],那么最大利润为6 - 1 = 5

暴力解法

双重循环,这个不用讲了,但是超时了

找最小值

public int maxProfit(int[] prices) {
    int max = 0, min = Integer.MAX_VALUE;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        } else {
            max = Math.max(max, prices[i] - min);
        }
    }
    return max;
}

这个算法的思路是在第i天买入,那么假设在未来的第j天卖掉可以获得最大值,那么如果在i到j天里我们找到一个时间k,且prices[k] < prices[i],那么最大利润将在k天买入,j天卖出达到。因此当遍历一遍数组时就可以得到最大利润

动态规划

 public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }

difference = prices[i] - prices[i-1]表示了每两天股票的差价,将问题转换为求连续子串的最大值,maxCur表示当前天数下的最大收益,maxSoFar表示总天数下的最大收益。 difference可能是个负数,但是只要maxCur大于0,那么表示在第i天卖出时还是赚钱的,如果求得的一个maxCur大于maxSoFar,更新maxSoFar的值

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容