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];
}