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)