image.png

解法

动态规划解法

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 第i天0代表持有股票最多金额
        // 1代表不持有股票最多金额
        int[][] dp = new int[len][2];
        dp[0][0] = - prices[0];
        for (int i = 1; i < len; i++) {
            // 只买卖一次，所以每次都是和-prices[i]对比，之前不会有利润
            dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
}

贪心算法

class Solution {
    public int maxProfit(int[] prices) {
        int low = Integer.MAX_VALUE;
        int maxRes = 0;
        for (int price : prices) {
            // 保留前面的最小值
            low = Math.min(low, price);
            // 计算价值最大值
            maxRes = Math.max(maxRes, price - low);    
        }
        return maxRes;
    }
}