[leetcode_122]Best Time to Buy and Sell Stock II

I used to think this problem was really hard, but the acceptance rate was so high. I was frustrated wondering why I couldn’t solve it.

Then yesterday, after solving Part I on a whim, everything suddenly clicked.

The problem requires that you must buy before you sell, and you can only buy again after selling. You can make multiple transactions. What is the maximum profit?

The solution: compute the day-to-day price differences, then sum up all the positive differences.

Accepted on the first try:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int sum = 0;
        if(prices.size() <= 0)
            return sum;
        vector<int> dis(prices.size()-1);
        for(int i = 1;i < prices.size();i++)
        {
            dis[i-1] = prices[i] - prices[i-1];
        }
        for(int i = 0;i < dis.size();i++)
        {
            if(dis[i] > 0)
            {
                sum += dis[i];
            }
        }
        return sum;
    }
};