Leetcode 121 买卖股票的最佳时机

题意理解：

        给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

        返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

        

        注意：这里只有一只股票，只进行一次买卖，求最大利益。

        所以：对于每一天，都有两个状态：持有股票、不持有股票

        这里定义一个二维dp数组：dp[0]表示持有股票能获得的最大收益，dp[0]表示不持有股票能获得最大大受益。

        对于不持有股票的状态：包含当天卖出

        持有股票状态：包含当前买入

解题思路：

        定义二维dp[]数组：

        dp[i][0]:表示持有股票能获得的最大收益

        dp[i][1]:表示不持有股票能获得最大大受益

        1.初始化

        dp[0][0]=-price[0];//买入所以当前收益为负

        dp[0][1]=0;//无交易，无收益

        2.递推公式

        dp[i][0]=max(之前买入，当前买入)=max(dp[i-1][0],-prices[i])

        dp[i][1]=max(之前卖出，今天卖出)=max(dp[i-1][1],dp[i-1][0]+prices[i])

1.解题

public int maxProfit(int[] prices) {int[][] dp=new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.length;i++){dp[i][0]=Math.max(dp[i-1][0],-1*prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}

2.分析

时间复杂度：O(n)

空间复杂度：O(2n)