连接:http://www.lintcode.com/zh-cn/problem/best-time-to-buy-and-sell-stock-ii/
假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
这一题很容易想到一个n方的dp，dp[i]表示前i天能得到的最大值， cost[i]表示价值。
如果第i个不卖出去，dp[i]=dp[i-1] (1)
如果第i个卖出去，dp[i]=max(dp[i], dp[k]+cost[i]-cost[k])，0<=k<i;(2)
这样虽然能得到正确的答案，但是会超时！！！！
以上的关键是(2)式比较耗时，我们可以优化下。
首先第i个卖出去的时候
1)这个票是从i-1买进来的，这个时候cost[i-1]一定要小于cost[i],否则这种情况不存在。
2)这个票是从i-1以前买进来的，设为第k天，这样的是有条件的，那就是cost[k+1]到cost[i-1]都介于cost[k]与cost[i]之间。否则取另外的就会有更优的解法。
从cost[k]买进来cost[i]卖出去，等价为cost[k]买进来cost[i-1]卖出去，然后再从cost[i-1]买进来cost[i]卖出去，cost[i]-cost[i-1]是个定值，所以就是直接考虑前i-1,
所以(2)式直接改成dp[i]=max(dp[i], dp[i-1]+cost[i]-cost[i-1])，就是直接考虑第i-1个就好了;所以就可以在O(n)时间复杂度内解决了。
AC代码:
class Solution { public: /** * @param prices: Given an integer array * @return: Maximum profit */ int maxProfit(vector<int> &prices) { int Size=prices.size(); int dp[Size+10]; int c[Size+10]; for(int i = 1; i <= Size; i++){ c[i]=prices[i-1]; } dp[1]=0; for(int i=2; i<=Size; i++){ dp[i]=dp[i-1]; if(c[i]>c[i-1]){ if(c[i]-c[i-1]+dp[i-1]) dp[i]=c[i]-c[i-1]+dp[i-1]; } } if(Size==0)return 0; return dp[Size]; } };
