[leetcode_123]Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock系列第三题。之前两题分别说可以买卖任意多次和只能买卖一次。
此题是买卖两次。
买卖两次，找个节点分割问题，就把问题变成两个买卖一次的问题。但是超时。时间复杂度要到o(n^2)
另外一个思路。
按照买卖一次的方法处理正序，逆序
然后存储到达每个点时的max值。线性解法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74


class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.size() <= 1) return 0;
        vector<int> dis;
        dis.clear();
        for(int i = 0; i < prices.size()-1; i++) {
            int val = prices[i+1] - prices[i];
            dis.push_back(val);
        }
        vector<int> cost;
        cost.clear();
        if(dis[0] <= 0) {
            cost.push_back(0);
        }
        else {
            cost.push_back(dis[0]);
        }
        for(int i = 1; i < dis.size(); i++) {
            if(cost[i-1] + dis[i] >= 0) {
                cost.push_back(cost[i-1] + dis[i]);
            }
            else {
                cost.push_back(0);
            }
        }
        int maxnow = 0;
        for(int i = 0; i < cost.size(); i++) {
            if(cost[i] < maxnow)
                cost[i] = maxnow;
            else {
                maxnow = cost[i];
            }
        }

        vector<int> cost_back;
        cost_back.clear();
        if(dis[dis.size()-1] <= 0) {
            cost_back.push_back(0);     
        }
        else {
            cost_back.push_back(dis[dis.size()-1]);
        }
        for(int i = dis.size() - 2; i >= 0; i--) {
            if(cost_back[dis.size()-2-i] + dis[i] >= 0) {
                cost_back.push_back(cost_back[dis.size()-2-i] + dis[i]);
            }
            else {
                cost_back.push_back(0);
            }
        }
        maxnow = 0;
        for(int i = 0; i < cost_back.size(); i++) {
            if(cost_back[i] < maxnow)
                cost_back[i] = maxnow;
            else {
                maxnow = cost_back[i];
            }
        }
        int max = 0;
        for(int i = 0; i < cost.size(); i++) {
            if(cost.size() - 2 - i >= 0 && cost.size() - 2 - i < cost.size()) {
                if(max < cost[i] + cost_back[cost.size()-2-i]) {
                    max = cost[i] + cost_back[cost.size()-2-i];
                }
            }
            else {
                if(max < cost[i])
                    max = cost[i];
            }
        }
        return max;
    }
};