思路1：

買的那天一定是賣的那天之前的最小值。 每到一天，維護(hù)那天之前的最小值即可。

假設(shè)第一天是最小值，最大值初始化為0，當(dāng)以后某天的價(jià)格小于最小值時(shí)，將最小值更新

當(dāng)天價(jià)格大于最小值，說(shuō)明有利可圖，就取之前的最大值，和當(dāng)天的收益之中的最大值當(dāng)做最大值。
?

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：動(dòng)態(tài)規(guī)劃

狀態(tài)：

• dp[i][0]?第 i 天持有股票的最大剩余現(xiàn)金；
• dp[i][1]?第 i 天不持有股票的最大剩余現(xiàn)金

初始化：

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

狀態(tài)轉(zhuǎn)換：

? ? ? ? //第i天不持有股票，分兩種情況，一種是已經(jīng)賣出或一直沒(méi)買入，那dp[i][0] = dp[i-1][0]

? ? ? ? 第二種是賣出，i天的價(jià)位加上i-1的剩余價(jià)值。兩種取最大值。

? ? ? ? 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++){//不持有股票=(賣出, 已經(jīng)賣出)dp[i][0] = getmax(dp[i-1][0], prices[i]+dp[i-1][0]);//持有股票=(買入, 已經(jīng)買入)dp[i][1] = getmax(dp[i-1][1], -prices[i]);}return dp[pricesSize-1][0];
}