题目描述

贪心算法

贪心算法的宗旨就是对于每一步的计算, 都只求当前局部的最优值, 然后所有的局部最优最终可以得到全局的最优.

在这道题中, 对于每一天的股票价格进行分析, 如果这一天的股票涨了, 那就记录下来, 如果下跌了那就不计入总的收益

所以每一天的收益只与前一天有关, 我们要做的就是把所有的正向收益都累加起来.

public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len < 2) {
        return 0;
    }
    int res = 0;

    for (int i = 0; i < len - 1; i++) {
        if (prices[i] < prices[i + 1])
            res += prices[i + 1] - prices[i];
    }
    return res;

}

动态规划

这道题与上一道题目的唯一区别是可以重复无数次的买卖操作

在上一道题中只允许买卖一次, 所以每次如果持有股票的话, 不能出现dp[i-1][0]-prices[i] , 这道题添加上这个情况即可

public int maxProfit(int[] prices) {

    int len = prices.length;
    if (len < 2) {
        return 0;
    }

    int[][] dp = new int[len][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (int i = 1; i < len; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

    return dp[len - 1][0];

}

动态规划压缩状态

因为遍历的过程中只涉及到两个dp值, 所以可以压缩状态释放空间:

public int maxProfit(int[] prices) {

    int len = prices.length;
    if (len < 2) {
        return 0;
    }

    int[] dp = new int[2];
    dp[0] = 0;
    dp[1] = -prices[0];

    for (int i = 1; i < len; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i]);
        dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    }

    return dp[0];

}