LeetCode/122.cpp at master · nitin-maharana/LeetCode · GitHub

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
/*
 * Written by Nitin Kumar Maharana
 * nitin.maharana@gmail.com
 */

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(!prices.size())
            return 0;

        for(int i = 0; i < prices.size()-1; i++)
            prices[i] = prices[i+1] - prices[i];

        prices.pop_back();

        int profit, maximum, maxSoFar;

        profit = maximum = maxSoFar = 0;

        for(int i = 0; i < prices.size(); i++)
        {
            maxSoFar += prices[i];

            if(maxSoFar > maximum)
                maximum = maxSoFar;
            else
            {
                profit += maximum;
                maxSoFar = (prices[i] < 0) ? 0 : prices[i];
                maximum = maxSoFar;
            }
        }

        profit += maximum;

        return profit;
    }
};