Java-LeetCode122. 买卖股票的最佳时机 II-动态规划 | 贪心算法

• 算法
  • 1.动态规划：dp[i][0]表示第i天没有持有股票的最大收益，dp[i][1]表示第i天持有这支股票的最大收益
  • 2.初始状态：dp[0][0] = 0;dp[0][1] = -prices[0];
  • 3.状态转移：
    • 第i天没有持有这只股票有两种情况：第i-1天也没有持有这只股票；第i-1天持有这只股票，第i天以prices[i]卖出
      • dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    • 第i天持有这只股票也有两种情况：第i-1天也持有这只股票；第i-1天没有持有这只股票，第i天以prices[i]买入
      • dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (int i = 1; i < n; ++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[n - 1][0];
}
// 优化空间
public int maxProfit(int[] prices) {
    int dp0 = 0, dp1 = -prices[0];
    for (int i = 1; i < prices.length; ++i) {
        int newDP0 = Math.max(dp0, dp1 + prices[i]);
        int newDP1 = Math.max(dp1, dp0 - prices[i]);
        dp0 = newDP0;
        dp1 = newDP1;
    }
    return dp0;
}

• 算法
  • 1.贪心算法
  • 2.股票买卖策略
    • 单独交易日：设今天价格p1、明天价格p2，则今天买入、明天卖出可赚取金额p2 - p1 (负值代表亏损)
    • 连续上涨交易日：设此上涨交易日股票价格分别为p1、p2、....，则第一天买最后-天卖收益最大，即pn-p1，等价于每天都买卖，即pn - p1 = (p2 - p1) + (p3- p2) + ... + (pn - pn-1)
    • 连续下降交易日：则不买卖收益最大，即不会亏钱
  • 3.遍历数组遇到上涨的就加上，遇到下降的就略过

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