买卖股票的最佳时机-贪心/动态规划-Java/python

日期：2023-09-15 17:52

一、题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。
返回你能获得的最大利润。

二、思路解析

**1.贪心算法，**一次遍历。题目转换为简单思路
要求的是在这些天里买卖股票获得的最大利润。
手上一次只能持有一个股票，在最好的时间买入卖出。
[7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。这个边界情况的确定一下子就变得简单了起来。
2.动态规划
DP动态规划，第i天只有两种状态，不持有或持有股票，当天不持有股票的状态可能来自昨天卖出或者昨天也不持有，同理，当天持有股票的状态可能来自昨天买入或者昨天也持有中，取最后一天的不持有股票状态就是问题的解

三、代码

1.思路清晰java代码

class Solution {public int maxProfit(int[] prices) {int ans=0;//初始收入for(int i=1;i<=prices.length-1;i++)//遍历{if(prices[i]>prices[i-1])//只要后边比前边大{ans+=prices[i]-prices[i-1];//就有获利空间}}return ans;//返回最后的收益}
}

2.动态规划python3

class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices:return 0n = len(prices)dp = [[0]*2 for _ in range(n)]# dp[i][0]表示第i天不持有股票, dp[i][1]表示第i天持有股票dp[0][0], dp[0][1] = 0, - prices[0]for i in range(1, n):dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])return dp[n-1][0]

3.动态规划java

public class Solution {public int maxProfit(int[] prices) {int len = prices.length;if (len < 2) {return 0;}// 0：持有现金// 1：持有股票// 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0int[][] 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];}
}

四、总结

1.贪心算法
今天价格小于明天价格就在今天买入然后明天卖出，时间复杂度O(n)

2.动态规划
时间复杂度：O(N)，这里 N 表示股价数组的长度；
空间复杂度：O(N)，虽然是二维数组，但是第二维是常数，与问题规模无关。

最近发表

猜你喜欢

买卖股票的最佳时机-贪心/动态规划-Java/python

一、题目

二、思路解析

三、代码

四、总结

相关文章