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;
}
LeetCode题解 文章被收录于专栏

测试

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
01-23 09:08
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-29 15:07
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
01-12 12:42
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议