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