买卖股票的最佳时机

原题链接

使用的方法

动态规划

解题思路

• 给定一个数组 prices，其中 prices[i] 是一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。
• 设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
• 我们可以使用动态规划的方法来解决这个问题。我们需要维护两个变量：一个是当前的最小价格 minPrice，另一个是当前的最大利润 ans。
• 我们遍历价格数组，对于每一天的价格 num，我们首先计算当前价格与 minPrice 之间的利润，并更新 ans 为当前利润和之前最大利润的较大值。然后，我们更新 minPrice 为当前价格和之前最小价格的较小值。
• 通过这种方式，我们可以在一次遍历中计算出最大利润，并最终返回 ans。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int minPrice = prices[0];
        for(int num : prices){
            ans = Math.max(ans,num - minPrice);
            minPrice = Math.min(minPrice,num);
        }
        return ans;
    }
}