LeetCode 5, Sell Stock II

发表于   |   分类于 ，   |     |   阅读次数

####题目
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

####思路

这道题我拖了好久才搞，刚开始没有看懂题目，觉得老复杂了是不是要用到动态规划贪心算法什么的，就搁置了很久。结果还是在网上看了提示才发现原来直接求递增序列的和就可以了。

如果把股票的价格画成曲线，那么我们只要去求所有递增区间的值就可以了，具体思路就是找到拐点，然后计算拐点之前最大值与最小值之间的差值，那么这就是我们所要求的利润。最后直到数组遍历结束。中间有个小插曲，在LeetCode上提交代码的时候，忘了判断边界，结果一直Runtime Error。

####代码

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
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty())
            return 0;
        int profit = 0;
        std::vector<int>::iterator it = prices.begin();
        int new_price = *it;
        int last_good_price = *it;
        while (it != prices.end()) {
            if (*it >= last_good_price) {
                last_good_price = *it;
                it++;
            }
            else {
                profit += (last_good_price - new_price);
                new_price = *it;
                last_good_price = *it;
                it++;
            }
        }
        profit += (last_good_price - new_price);
        return profit;
    }
};