Best Time to Buy and Sell Stock
给出n天中每天的股票市值，选定合适的时间买进和卖出一次，问最多赚多少
一开始想都没想O(n^2)暴力一次，果然TLE
然后想到股票市值按日期两两相减，然后就是求最大子段和的问题了。。下面两种写法这题都ok，但做Maximum Subarray这题的时候发现第二种写法是错的，因为存在数列全负的情况！
Maximum Subarray
裸的求最大子段和的问题，跟上题一样。。
1 class Solution {
2 public:
3 int maxProfit(vector<int> &prices) {
4 int profit[100010], dp[100010], mx = 0, tp = 0, n = prices.size();
5 for(int i = 0; i < n - 1; ++i) {
6 profit[i + 1] = prices[i + 1] - prices[i];
7 }
8 dp[0] = 0;
9 for(int i = 1; i < n; ++i) {
10 tp += profit[i];
11 if(tp > mx) {
12 mx = tp;
13 dp[i] = mx;
14 }
15 else
16 dp[i] = dp[i - 1];
17 if(tp < 0) tp = 0;
18 }
19 return mx;
20 }
21 };
1 class Solution {
2 public:
3 int maxProfit(vector<int> &prices) {
4 int profit[100010], dp[100010], mx = 0, n = prices.size();
5 for(int i = 0; i < n - 1; ++i) {
6 profit[i + 1] = prices[i + 1] - prices[i];
7 }
8 dp[0] = 0;
9 for(int i = 1; i < n; ++i) {
10 if(dp[i - 1] + profit[i] < 0) dp[i] = 0;
11 else
12 dp[i] = dp[i - 1] + profit[i];
13 if(dp[i] > mx) mx = dp[i];
14 }
15 return mx;
16 }
17 };