[数据结构与算法]买卖股票的最佳时机-贪心/动态规划-Java/python

一、题目

给你一个整数数组 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 0
        n = 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 → 0
        int[][] 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)，虽然是二维数组，但是第二维是常数，与问题规模无关。