leetCode买卖股票的最佳时机II(题号122)

这篇具有很好参考价值的文章主要介绍了leetCode买卖股票的最佳时机II(题号122)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

122. 买卖股票的最佳时机 II

一.题目

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1:

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
 二    总利润为 4 + 3 = 7 。

示例 2:

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
示例 3:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 

提示:

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

二.解题思路

动态规划解法:

dp[i][0] 表示第i天持股票数0

dp[i][1] 表示第i天持股票数1

第i-1天:

1.持股票数0,不买入 ,第i天持股票数:0

2.持股票数0,买入 -price[i-1],第i天持股票数:1

3.持股票数1,不卖出,第i天持股票数:1

4.持股票数1,卖出 +price[i-1],第i天持股票数:0

状态转移方程:

  dp[i][0]=max(情况1,情况4);

  dp[i][0]=max(dp[i-1][0] , dp[i-1][1]+price[i]);

  dp[i][1]=max(情况2,情况3);

  dp[i][1]=max(dp[i-1][0]-price[i] , dp[i-1][1]);文章来源地址https://www.toymoban.com/news/detail-653585.html

三.解题代码

public class Solution {
    public int maxProfit(int[] prices) {


        int n=prices.length;
        int[][] dp=new int[n][2];

        dp[0][0]=0; //第0天不持股 
        dp[0][1]=-prices[0];//第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 Math.max(dp[n-1][0],dp[n-1][1]);
    }
}

到了这里,关于leetCode买卖股票的最佳时机II(题号122)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 贪心算法|122.买卖股票的最佳时机II

    力扣题目链接 贪心思路出来了,代码居然如此简单啊! 本题首先要清楚两点: 只有一只股票! 当前只有买股票或者卖股票的操作 想获得利润至少要两天为一个交易单元。 #贪心算法 这道题目可能我们只会想,选一个低的买入,再选个高的卖,再选一个低的买入.....循环反复

    2024年04月16日
    浏览(31)
  • [Java·算法·中等] LeetCode122. 买股票的最佳时机 II 解读

    人不走空                                                                          目录         🌈个人主页:人不走空       💖系列专栏:算法专题 ⏰诗词歌赋:斯是陋室,惟吾德馨 题目 示例 示例1 示例2 示例3  提示  详细解读 作者其他作品:   给你一

    2024年02月19日
    浏览(32)
  • 【DP】【贪心】122.买卖股票的最佳时机II

    题目 六种股票问题总结https://blog.csdn.net/weixin_47692079/article/details/117202705

    2024年01月19日
    浏览(40)
  • 122.买卖股票的最佳时机II(不限次数)

    labuladong的状态图解

    2024年02月04日
    浏览(56)
  • 算法 贪心2 || 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

    如果想到其实 最终利润是可以分解的 ,那么本题就很容易了! 如何分解呢? 假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。 相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。 此时就是把利润分解为每天为单位的维度,而不是从0天到第3天整体去

    2023年04月13日
    浏览(46)
  • 代码随想录 第三十二天 45.跳跃游戏 II||122.买卖股票的最佳时机 II55. 跳跃游戏

    力扣题目链接(opens new window) 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例  1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位

    2024年02月15日
    浏览(54)
  • Day32 贪心算法 part02 122. 买卖股票的最佳时机 II 55. 跳跃游戏 45. 跳跃游戏 II

    思路:计算每天的利润,利润如果为正,加到结果中去

    2024年01月19日
    浏览(44)
  • 算法刷题|121.买卖股票的最佳时机、122.买卖股票的最佳时机Ⅱ

    题目:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获

    2023年04月26日
    浏览(41)
  • 《LeetCode》—— 买卖股票的最佳时机

    本期,我将给大家讲解的是有关动态规划类的题—— 买卖股票的最佳时机 。这个系列总共有四道题。接下来,让我们一起去看看!!! 目录 (一)买卖股票的最佳时机 (二)买卖股票的最佳时机 II (三)买卖股票的最佳时机 III (四)买卖股票的最佳时机 IV LeetCode题目链

    2024年02月05日
    浏览(46)
  • leetcode 121. 买卖股票的最佳时机

             本题用dp算法做, dp[i]的含义:前 i+1天能获得的最大利润 。 然后每次循环时需要维护一个最小值 min_num :即 i+1天中股票的最低价 。剩下的步骤都很常规,代码如下:         dp[i][0]:第i天持有股票所拥有的最多现金。          dp[i][1]:第i天不持有股票所拥有的最

    2024年02月12日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包