Best Time to Buy and Sell Stock II Solutions in C++

// Source : https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
// Author : Hao Chen
// Date   : 2014-06-18



class Solution {
public:
    int maxProfit(vector<int>& prices) {
        return maxProfit02(prices);
        return maxProfit01(prices);
    }
    // Solution 1 
    // find all of ranges: which start a valley with the nearest peak after
    // add their delta together 
    //
    int maxProfit01(vector<int> &prices) {

        int max = 0;
        int low = -1;
	int len = prices.size();
        for (int i=0; i < len - 1; i++){
            //meet the valley, then goes up
            if (prices[i] < prices[i+1] && low < 0 ) {
                low = i;
            }
            //meet the peak, then goes down
            if (prices[i] > prices[i+1] && low >= 0) {
                max += ( prices[i] - prices[low] ) ;
                low = -1; // reset the `low`
            }
        }

        // edge case
        if ( low >= 0 ) {
            max += ( prices[prices.size()-1] - prices[low] );
        }

        return max;
    }

    // Solution 2 
    // if we find we can earn money, we just sell
    int maxProfit02(vector<int>& prices) {
        int profit = 0 ;
        for(int i=1; i< prices.size(); i++) {
            profit += max(0, prices[i] - prices[i-1]);
        }
        return profit;
    }
};

#include <vector>
using std::vector;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int profit = 0;
        for (auto i = prices.begin(); i != prices.end(); ++i)
            if (i+1 != prices.end() && *(i+1) > *i) profit += *(i+1) - *i;
        return profit;
    }
};

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
/// Author : liuyubobobo
/// Time   : 2017-10-22

#include <iostream>
#include <vector>

using namespace std;

/// Find every peak and vally in prices
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        if(prices.size() == 0)
            return 0;

        vector<int> peakAndValley;
        peakAndValley.push_back(0);
        int i = 1;
        while(i < prices.size()){

            while(i < prices.size() && prices[i] >= prices[i-1])
                i ++;
            if(i-1 != peakAndValley.back())
                peakAndValley.push_back(i-1);

            while(i < prices.size() && prices[i] <= prices[i-1])
                i ++;
            if(i-1 != peakAndValley.back())
                peakAndValley.push_back(i-1);
        }

//        cout << "peakAndvalley size = "<< peakAndValley.size() << endl;
//        for(int i = 0 ; i < peakAndValley.size() ; i ++)
//            cout << peakAndValley[i] << ((i == peakAndValley.size() - 1) ? "\n" : " ");

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

        return res;
    }
};

int main() {

    int prices1[] = {1, 2};
    vector<int> pricesVec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
    cout << Solution().maxProfit(pricesVec1) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
/// Author : liuyubobobo
/// Time   : 2017-10-22

#include <iostream>
#include <vector>

using namespace std;

/// Every rise price can be a part of profit
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

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

        return res;
    }
};

int main() {

    int prices1[] = {1, 2};
    vector<int> pricesVec1(prices1, prices1 + sizeof(prices1)/sizeof(int));
    cout << Solution().maxProfit(pricesVec1) << endl;

    return 0;
}