121 买入股票的最佳时机

思路1：

买的那天一定是卖的那天之前的最小值。 每到一天，维护那天之前的最小值即可。

假设第一天是最小值，最大值初始化为0，当以后某天的价格小于最小值时，将最小值更新

当天价格大于最小值，说明有利可图，就取之前的最大值，和当天的收益之中的最大值当做最大值。
 

int maxProfit(int* prices, int pricesSize) 
{
	int maxleft;
	int minv=prices[0];
	
	
	if (pricesSize == 1)
		return 0;

	int i = 1;
	int j = 0;
	int maxv = 0;
	for(i; i < pricesSize; i++)
	{
		if (prices[i] > minv)
		{
			maxv = getmax(maxv, prices[i]-minv);
		}
		else
		{
			minv = prices[i];
		}
	}

	return maxv;
}

思路2：动态规划

状态：

• dp[i][0] 第 i 天持有股票的最大剩余现金；
• dp[i][1] 第 i 天不持有股票的最大剩余现金

初始化：

      dp[0][0] = 0            //不持有股票，不买入
      dp[0][1] = -prices[0]  //买入

状态转换：

        //第i天不持有股票，分两种情况，一种是已经卖出或一直没买入，那dp[i][0] = dp[i-1][0]

        第二种是卖出，i天的价位加上i-1的剩余价值。两种取最大值。

        dp[i][0] = getmax(dp[i-1][0], prices[i]+dp[i-1][0]); 

       //第i天持有股票，分两种，一种是刚买入，dp[i][1] = -prices[i], 第二种是保持持有dp[i][1] = dp[i-1][1]

        dp[i][1] = getmax( -prices[i],dp[i-1][1] )

int maxProfit(int* prices, int pricesSize) 
{
	int dp[pricesSize][2];

	memset(dp, 0, sizeof(dp));
	dp[0][0] = 0;
	dp[0][1] = -prices[0];

	if (pricesSize == 1)
		return 0;

	int i = 1;
	for(i; i < pricesSize; i++)
	{
		//不持有股票=(卖出, 已经卖出)
		dp[i][0] = getmax(dp[i-1][0], prices[i]+dp[i-1][0]);
		
		//持有股票=(买入, 已经买入)
		dp[i][1] = getmax(dp[i-1][1], -prices[i]);
	}

	return dp[pricesSize-1][0];
}