leetcode Best Time to Buy and Sell Stock

本次题解包括

  • 121 Best Time to Buy and Sell Stock
  • 122 Best Time to Buy and Sell Stock II
  • 123 Best Time to Buy and Sell Stock III
  • 188 Best Time to Buy and Sell Stock IV
  • 714. Best Time to Buy and Sell Stock with Transaction Fee

121 Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

传送门

题意:给定股票每日的售价,求 一次买进和一次卖出最多可以获取多大利润?

思路:其实就是求买进时和卖出是最大差价。每次更新当前最小价格,dp即可。

 

 

 

 

 

122 Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

传送门

题意:给定股票每日的售价,求 若干次买卖最多可以获取多大利润?

思路:其实就是求股票低价买,高价卖最多能获得多少钱。求连续上升的高度和。

如12314为 1买进3卖出1买进4卖出。

 

 

 

 

 

123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目地址:Best Time to Buy and Sell Stock III

题意:给定股票每日的售价,求最多两次买卖最多可以获取多大利润?

思路:DP。

设dp[i]为到第i天能获取的最大值。(类似121题)求出dp后,逆向扫描数组。

nax_price为最大售价,每次减去price[i]得到第i天之后的利润,加上dp[i – 1]即为两次买卖的值。

C++

Python

 

 

 

 

 

 

188. Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目地址:Best Time to Buy and Sell Stock IV

题意:给定股票每日的售价,求最多k次买卖最多可以获取多大利润?

思路:dp

设dp[i][x]为第i天第x次交易的最大利润,则容易写出dp方程:

  • dp[i][x] = max(dp[i-1][x] , dp[j][x – 1] + prices[i] – prices[j])  0 <= j < i
  • 上面的状态转移方程第一项为第i天不进行交易,第二项为枚举j 从0~i-1,第j天买入,第i天卖出

注意当k >= len(prices) / 2的时候,说明相当于无限次交易,和第122题Best Time to Buy and Sell Stock II 一样。

上面的复杂度为O(kn^2)代码如下:

C++

 

可以对上面的代码优化,注意到枚举j是为了寻找第i天之前交易x-1次的利润最大,而这个过程重复计算了很多,可以进行优化,只需要保存i之前最大的dp[j][x – 1] – prices[j]即可。这样复杂度就变为O(nk)

空间复杂度上也可以进一步优化为O(n)

 

之前的写法:

dp,设dp[i][j]为第J天进行第i次交易能获取的最大值。

  • 当k >=n/2时候,相当于第122题。Best Time to Buy and Sell Stock II
  • dp[i][j]=max(dp[i][j-1],prices[j] + maxTemp)  我们能获取的最大利润,当我们在第j天进行抛售时。由于maxTemp已经算了买进时的价格,所以直接加上即可。
  • maxTemp =max(maxTemp,dp[i-1][j-1] – prices[j])  可以理解为已获得的最大利润,即如果买进第j天的,那么用之前一轮的买卖,前一天的的利润即(dp[i-1][j-1])减去prices[j]

 

 


 

714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Note:

 

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

 

题目地址:leetcode Best Time to Buy and Sell Stock with Transaction Fee

题目大意:给定股票的价格,以及每次交易需要的花费fee,求能获得的最大利润

思路:

双状态DP,类似于Best Time to Buy and Sell Stock with Cooldown

sell 考虑第i天是否卖出,buy考虑第i天是否买入

则有:

  • sell = max(sell, buy + prices[i] – fee)
  • buy = max(buy, sell – prices[i])

C++

Java

Python

本文是leetcode如下的题解

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Best Time to Buy and Sell Stock
本文地址:https://www.hrwhisper.me/leetcode-best-time-to-buy-and-sell-stock-i-ii-iii-iv/

听说长得好看的已经打赏了

Leetcode , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *