🚩买卖股票的最好时机(二)

🏳️‍🌈1.题目描述

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票

2. 如果不能获取收益，请返回0

3. 假设买入卖出均无手续费

数据范围： 1≤n≤1×10^5 ， 1≤ prices ≤10^4

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例1

输入：

[8,9,2,5,4,7,1]

返回值：

7

说明：

在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3 总获利1+3+3=7，返回7

🏳️‍🌈2.题目分析

在第一题的基础上增加了可以多次买卖该只股票，那我们就不能用只买卖一次的思路思考，多次进行买卖然后求最大值，我们不能使用简单暴力法了，因为我们不知道总共需要进行多少次买卖。那我们就还使用动态规划模拟所有情况

思路1：动态规划

与第一题分析思路类似

dp[i][0] //表示第 i+1天没有持有股票  (i是从0开始)
dp[i][1] //表示第 i+1天持有股票  

推导状态转移方程：

• 对于dp[i][0] 可能有两种情况：

1. dp[i-1][0] 前一天没有持有股票，当天也不购买股票
2. dp[i-1][1] +prices[i] 前一天持有股票，当天卖出

   dp[i][0] 就是 两种情况的最大值

• 对于dp[i][1] 有两种情况：

1. 可以多次买卖，前一天没有持有股票，当天购买股票就是 dp[i-1][0]-prices[i]

   1. 前一天持有股票，当天不进行任何操作 dp[i-1][1]

dp[i][1] 就是 两种情况的最大值

 //动态转移方程
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            
 dp[i][1] = Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);

结果是最后一天不持有股票的值 dp[n-1][0]

思路2：贪心（一次遍历）

股票的变化是光滑的直线，由图可知每次买卖都是 极小值买入 极大值卖出，根据极小值极大值定义，极小值之后一定是递增的，那么在遇到极大值之前这之间的每个值 - 前面的值 就是最终 极大值 - 极小值（类似于差分，把一段上升直线的分成若干小段，每一小段增加的量累加到一起，就是整个上升直线的最大差值）

转化成编程思路 就是 如果 某一天比前一天股票的价格高，那么就进行买卖

    if(prices[i] > prices[i-1]){
       sum += prices[i] - prices[i-1];
         }

🏳️‍🌈3.代码实现

动态规划 代码实现：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
          int n = prices.length;
        
        //下标i是从0开始
        //dp[i][0] 表示第i+1天不持有股票 从第一天到第i+1天的收益
        //dp[i][1] 表示第i+1天持有股票 从第一天到第i+1天的收益
      int[][] dp = new int[n][2];
        //初始化第一天不持有股票的收益0
        dp[0][0] = 0;
        //初始化第一天持有股票的收益 就是第一天买了当天的股票 -prices[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][0]-prices[i],dp[i-1][1]);
        }
        
        //最后一天不持有股票此时的值就是最大收益
        return dp[n-1][0];
    }
}

贪心 代码实现：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
          int n = prices.length;
        int sum = 0;
        
        for(int i = 1; i < n; i++){
            if(prices[i] > prices[i-1]){
                sum += prices[i] - prices[i-1];
            }
        }
     return sum;
    }
}