[leetcode_121]Best Time to Buy and Sell Stock

I honestly didn’t expect to solve this one on my own, and the process was quite a journey. Persistence pays off!

The problem is roughly: you are trading stocks and can only make one transaction (buy once, sell once). On which day should you buy and on which later day should you sell to maximize profit?

I thought this would be easy – just brute force it. Of course, that resulted in TLE.

Then I racked my brain trying to figure out how to reduce the time complexity. Sorting? Greedy? It felt similar to the 2Sum problem, especially after drawing vertical lines on a graph.

Then it hit me: the difference between consecutive days represents the price change. If I compute these differences and then find the maximum contiguous subarray sum, the problem is solved!

I gave it a try and – AC!

Here is the code:

 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
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int max = 0;
        if(prices.size() <= 1)
            return max;
        vector<int> dis(prices.size()-1);
        for(int i = 1;i < prices.size();i++) {
            dis[i-1] = prices[i] - prices[i-1];
        }
        vector<int> value(dis.size());
        for(int i = 0;i < dis.size();i++) {
            value[i] = dis[i];
        }
        if(dis[0] < 0)
            value[0] = 0;
        else
            value[0] = dis[0];
        for(int i = 1;i < value.size();i++) {
            if(value[i-1] + value[i] < 0) {
                value[i] = 0;
            } else {
                value[i] = value[i-1] + value[i];
            }
        }
        for(int i = 0;i < value.size();i++) {
            if(value[i] > max) {
                max = value[i];
            }
        }
        return max;
    }
};