【算法分析与设计】买卖股票的最佳时机||

?

? ? ? ?📝个人主页：五敷有你? ? ??
?🔥系列专栏：算法分析与设计
??稳中求进，晒太阳

题目

给你一个整数数组?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 。

?思路

贪心算法

由于不需要限制交易次数，只要今天的价格比昨天高就交易。

采取最高点卖出的思想。一旦第二天下滑，就在前一天卖出去。比原来的快一点。

动态规划

定义状态：

????????我们定义状态来表示在某个时刻结束时的情况。在股票买卖问题中，一般会定义两种状态，分别是持有股票和不持有股票。

初始化状态：

????????设置初始状态，即在第一天结束时的情况。对于不持有股票的状态，初始利润为 0；对于持有股票的状态，初始利润为负的股票价格。

状态转移方程：

???????? 确定状态之间的转移关系。在股票买卖问题中，每天的状态可能来自前一天的状态。具体地，不持有股票的状态可能来自前一天不持有股票或前一天持有股票并卖出；持有股票的状态可能来自前一天持有股票或前一天不持有股票并买入。

迭代计算：

????????使用迭代的方式，从第二天开始更新状态，直到最后一天。每一天的状态都依赖于前一天的状态。

最终结果：

????????最终的最大利润通常对应于不持有股票的状态，因此返回该状态的利润作为最终结果。

方案一（贪心算法）

算法分析与设计

1. 从左到右遍历股票价格数组，寻找价格下降的趋势，即找到局部最小值。
2. 当找到局部最小值时，计算卖出该位置的股票所能获得的利润，并更新 now 变量为当前位置。
3. 继续遍历直到找到价格上升的趋势，即找到局部最大值。
4. 当找到局部最大值时，同样计算卖出该位置的股票所能获得的利润，并更新 now 变量为当前位置。
5. 重复上述过程直到遍历完整个股票价格数组。

代码实现

class Solution {
    public int maxProfit(int[] prices) {
            int n=prices.length;
            int now=0;
            int maxProfit=0;
            if(n==1){
                return 0;
            }
            for(int i=1;i<prices.length;i++){
                if(prices[i-1]>prices[i]){
                    maxProfit=maxProfit+prices[i-1]-prices[now];
                    now=i;
                   
                }
                if(i==n-1){
                    maxProfit=maxProfit+prices[i]-prices[now];
                }
            }
            
            return maxProfit;
    }
}

运行结果

时间复杂度O(n)

空间复杂度O(1)

?

方案二（动态规划）

算法分析与设计

定义状态：

dp[i][0] 表示第 i 天结束时不持有股票的最大利润。

dp[i][1] 表示第 i 天结束时持有股票的最大利润。

初始化状态：

dp[0][0] = 0：第一天结束时不持有股票，利润为 0。

dp[0][1] = -prices[0]：第一天结束时持有股票，利润为负的股票价格。

状态转移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])：不持有股票的状态可以来自前一天不持有股票或前一天持有股票并卖出。

dp[i][1] = max(dp[i-1][1], -prices[i])：持有股票的状态可以来自前一天持有股票或前一天不持有股票并买入。

迭代计算：

从第二天开始，使用循环迭代计算状态数组中的值，直到最后一天。

最终结果：

最终的最大利润通常对应于不持有股票的状态，因此返回 dp[n-1][0]，其中 n 是股票价格数组的长度。

代码实现

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        
        // 定义状态数组
        // dp[i][0] 表示第 i 天结束时不持有股票的最大利润
        // dp[i][1] 表示第 i 天结束时持有股票的最大利润
        int[][] dp = new int[n][2];
        
        // 初始状态
        dp[0][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];
    }
}

运行结果

时间复杂度O(n)

空间复杂度O(n)

这道题的效率确实不如贪心算法。。。

。?