#yyds干货盘点# 面试必刷TOP101：买卖股票的最好时机(二)

1.简述：

描述

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

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

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

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

数据范围：  ， 

要求：空间复杂度 ，时间复杂度 

进阶：空间复杂度 ，时间复杂度 

示例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

输入：

[5,4,3,2,1]

返回值：

0

说明：

由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。

示例3

输入：

[1,2,3,4,5]

返回值：

4

说明：

第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

2.代码实现：

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int n = prices.length;
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2]; 
        //第一天不持股，总收益为0
        dp[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]; 
    }
}