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

// Source : https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
// Author : Hao Chen
// Date   : 2014-08-22




class Solution {
public:
    // Dynamic Programming
    //
    //     Considering prices[n], and we have a position "i", we could have
    //       1) the maxProfit1 for prices[0..i]  
    //       2) the maxProfit2 for proices[i..n]
    //
    //    So, 
    //      for 1) we can go through the prices[n] forwardly.
    //          forward[i] = max( forward[i-1], price[i] - lowestPrice[0..i] ) 
    //      for 2) we can go through the prices[n] backwoardly.
    //          backward[i] = max( backward[i+1], highestPrice[i..n] - price[i]) 
    //
    int maxProfit(vector<int> &prices) {
        if (prices.size()<=1) return 0;
        
        int n = prices.size();
        
        vector<int> forward(n);
        forward[0] = 0;
        int lowestBuyInPrice = prices[0];
        for(int i=1; i<n; i++){
            forward[i] = max(forward[i-1], prices[i] - lowestBuyInPrice);
            lowestBuyInPrice = min(lowestBuyInPrice, prices[i]);
        }
        
        vector<int> backward(n);
        backward[n-1] = 0;
        int highestSellOutPrice = prices[n-1];
        for(int i=n-2; i>=0; i--){
            backward[i] = max(backward[i+1], highestSellOutPrice - prices[i]);
            highestSellOutPrice = max(highestSellOutPrice, prices[i]);
        }
        
        int max_profit = 0;
        for(int i=0; i<n; i++){
            max_profit = max(max_profit, forward[i]+backward[i]);
        }
        
        return max_profit;
    }
};

#include <cstddef>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    void moveNode(ListNode **destRef, ListNode **sourceRef) {
        ListNode *newNode = *sourceRef;
        *sourceRef = newNode->next;
        newNode->next = *destRef;
        *destRef = newNode;
    }
    ListNode *sortedMerge(ListNode *a, ListNode *b) {
        ListNode *ret = nullptr, **lastPtrRef = &ret;
        for (; a && b; lastPtrRef = &((*lastPtrRef)->next)) {
            if (a->val <= b->val) moveNode(lastPtrRef, &a);
            else moveNode(lastPtrRef, &b);
        }
        *lastPtrRef = a ? a : b;
        return ret;
    }
    void frontBackSplit(ListNode *source, ListNode **frontRef, ListNode **backRef) {
        if (source == nullptr || source->next == nullptr) {*frontRef = source; *backRef = nullptr;}
        else {
            ListNode *slow = source, *fast = source->next;
            while (fast != nullptr) {
                fast = fast->next;
                if (fast != nullptr) {
                    slow = slow->next;
                    fast = fast->next;
                }
            }
            *frontRef = source;
            *backRef = slow->next;
            slow->next = nullptr;
        }
    }
    void mergeSort(ListNode **headRef) {
        ListNode *head = *headRef, *front, *back;
        if (head == nullptr || head->next == nullptr) return;
        frontBackSplit(head, &front, &back);
        mergeSort(&front);
        mergeSort(&back);
        *headRef = sortedMerge(front, back);
    }
public:
    ListNode *sortList(ListNode *head) {
        mergeSort(&head);
        return head;
    }
};

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

#include <iostream>
#include <vector>

using namespace std;

/// Using first and second to trace all the possible transactions
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

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

        // first[i] is the max profit within day[0...i]
        vector<int> first(prices.size(), 0);
        int minPrice = prices[0];
        for(int i = 1 ; i < prices.size() ; i ++){
            first[i] = max(first[i-1], prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }

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

        // second[i] is the max profit within day[i...n)
        vector<int> second(prices.size(), 0);
        int maxPrice = prices.back();
        for(int i = prices.size() - 2 ; i >= 0 ; i --){
            second[i] = max(second[i+1], maxPrice - prices[i]);
            maxPrice = max(maxPrice, prices[i]);
        }

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

        int res = second[0];
        for(int i = 0 ; i < prices.size()-1 ; i ++)
            res = max(res, first[i] + second[i+1]);
        res = max(res, first.back());

        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-iii/description/
/// Author : liuyubobobo
/// Time   : 2017-10-22

#include <iostream>
#include <vector>

using namespace std;

/// Using hold and cash to trace the max money in different state
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {

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

        int hold1 = INT_MIN;
        int cash1 = 0;
        int hold2 = INT_MIN;
        int cash2 = 0;
        for(int price : prices) {
            cash2 = max(cash2, hold2 + price);
            hold2 = max(hold2, cash1 - price);
            cash1 = max(cash1, hold1 + price);
            hold1 = max(hold1, -price);
        }

        return cash2;
    }
};

int main() {

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

    return 0;
}