leetcode_best_time_to_buy_and_sell_stock_iii

发表于

难度：Hard

解题思路：最多两次交易，求最大收益。可以从这一系列的一次交易，求最大收益开始。先求出最大收益区间，然后在区间的前面，内部，后面，寻找第二个交易，使其最大。
求内部时。

1 2 3 5 2 8，假设求得最大收益是1～8的区间，在此区间寻找第二个交易，则为8-2+5-1。
又可以表达为8-1+5-2。5-2，这不就是[2 3 5 2]逆向的最大交易嘛？！

代码如下：

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
75
76
77
78
79
80
81
82
83
84
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2) return 0;
        int max_profit = 0;
        int min_price = prices.front(), max_price = prices.front();
        auto min_it = prices.begin(), max_it = prices.begin();
        auto final_min_it = min_it, final_max_it = max_it;
        for(auto it = prices.begin(); it != prices.end(); it++)
        {
            if(*it > max_price)
            {
                max_price = *it;
                max_it = it;
                if(max_price - min_price > max_profit)
                {
                    max_profit = max_price - min_price;
                    final_max_it = max_it;
                    final_min_it = min_it;
                }
            }
            if(*it < min_price)
            {
                min_price = *it;
                max_price = *it;
                min_it = it;
                max_it = it;
            }
        }
        if(max_profit == 0) 
            return 0;
        std::cout<<*final_max_it<<" "<<*final_min_it<<std::endl;
        int left_max_profit = cal_max_profit_with_iter(prices.begin(), final_min_it);
        int mid_max_profit = cal_max_profit_with_reverse_iter(final_max_it-1, final_min_it);
        int right_max_profit = cal_max_profit_with_iter(final_max_it+1, prices.end());
        
        int second_max_profit = max(left_max_profit, mid_max_profit);
        std::cout<<"left_max_profit"<<left_max_profit<<std::endl;
        std::cout<<"mid_max_profit"<<mid_max_profit<<std::endl;
        std::cout<<"right_max_profit"<<right_max_profit<<std::endl;
        second_max_profit = max(second_max_profit, right_max_profit);
        max_profit += second_max_profit;
        return max_profit;
    }
    
    int cal_max_profit_with_iter(const vector<int>::iterator& begin_it,const vector<int>::iterator &end_it) {
        if(begin_it == end_it) return 0;
        int max_profit = 0;
        int min_price = *begin_it, max_price = *begin_it;
        for(auto it = begin_it; it != end_it; it++)
        {
            if(*it > max_price)
            {
                max_price = *it;
                max_profit = max(max_price-min_price, max_profit);
            }
            if(*it < min_price)
            {
                min_price = *it;
                max_price = *it;
            }
        }
        return max_profit;
    }
    int cal_max_profit_with_reverse_iter(const vector<int>::iterator& begin_reverse_it,const vector<int>::iterator &end_reverse_it) {
        if(begin_reverse_it == end_reverse_it) return 0;
        int max_profit = 0;
        int min_price = *begin_reverse_it, max_price = *begin_reverse_it;
        for(auto it = begin_reverse_it; it != end_reverse_it; it--)
        {
            if(*it > max_price)
            {
                max_price = *it;
                max_profit = max(max_price-min_price, max_profit);
            }
            if(*it < min_price)
            {
                min_price = *it;
                max_price = *it;
            }
        }
        return max_profit;
    }
};

代码结果：9ms，超过23.79%

不使用迭代器，再写一次代码。

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
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() < 2)
            return 0;
        auto first_ret = find_single(prices,0,prices.size()-1);
        if(first_ret.second.first == first_ret.second.second)
            return 0;
        auto second_left = find_single(prices,0,first_ret.second.first);
        auto second_right = find_single(prices,first_ret.second.second,prices.size()-1);
        int second_mid = find_single_reverse(prices,first_ret.second.first,first_ret.second.second);
        int second_max = max(second_left.first,max(second_right.first,second_mid));
        return first_ret.first+second_max;
    }
    pair<int,pair<int,int>> find_single(vector<int>& prices, int low, int high)
    {
        int max_profit = 0;
        int cur_left = low;
        int max_left = low;
        int max_right = low;
        int min_price = prices[low];
        for(int i = low+1; i <= high; i++)
        {
            if(prices[i]-min_price > max_profit)
            {
                max_profit = prices[i]-min_price;
                max_left = cur_left;
                max_right = i;
            }
            if(prices[i] < min_price)
            {
                min_price = prices[i];
                cur_left = i;
            }
        }
        return make_pair(max_profit,make_pair(max_left,max_right));
    }
    
    int find_single_reverse(vector<int>& prices, int low, int high)
    {
        int max_profit = 0;
        int min_price = prices[high];
        int max_price = prices[high];
        for(int i = high-1; i >= low; i--)
        {
            if(prices[i] > max_price)
            {
                max_price = prices[i];
                max_profit = max(max_profit, max_price-min_price);
            }
            if(prices[i] < min_price)
            {
                min_price = prices[i];
                max_price = prices[i];
            }
        }
        return max_profit;
    }
};

运行时间：6ms，超过80.88%