121.买卖股票的最佳时机

睡醒就学

于 2022-07-21 10:55:49 发布

阅读量142

点赞数

分类专栏： LeetCode HOT100 文章标签： leetcode java

本文链接：https://blog.csdn.net/acm_xx/article/details/125907765

版权

LeetCode HOT100 专栏收录该内容

11 篇文章

订阅专栏

本文介绍了一种使用动态规划解决股票交易问题的方法，通过计算每日可能的最大收益，找到在给定股票价格数组中买入并卖出的最优策略，以实现最大利润。算法详细解释了如何利用前i天的最小价格与当前价格比较来确定收益，并提供了Java代码示例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题干： 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
在这里插入图片描述
题解： 直接暴力求解会超时，所以用动态规划，前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

class Solution {
    public int maxProfit(int[] prices) {
        int minp = prices[0];
        int len = prices.length;
        int[] maxp = new int[len];
        maxp[0] = 0;
        for(int i=1; i<len; i++){
            maxp[i] = Math.max(maxp[i-1], prices[i]-minp);
            minp = Math.min(minp, prices[i]);
        }
        return maxp[len-1];
    }
}