Best Time to Buy and Sell Stock
給出n天中每天的股票市值，選定合適的時間買進(jìn)和賣出一次，問最多賺多少
一開始想都沒想O(n^2)暴力一次，果然TLE
然后想到股票市值按日期兩兩相減，然后就是求最大子段和的問題了。。下面兩種寫法這題都o(jì)k，但做Maximum Subarray這題的時候發(fā)現(xiàn)第二種寫法是錯的，因?yàn)榇嬖跀?shù)列全負(fù)的情況！
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 };