Leetcode - Best Time to Buy and

题目链接

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time
(ie, you must sell the stock before you buy again).

解题思路

TODO （稍后补上）

解题代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        if (prices.empty())return 0;
        int *leftMax = new int[prices.size()];
        int *rightMax = new int[prices.size()];
        int minVal = prices[0];
        int profitMax = 0;
        for (int i =0;i<prices.size();i++) {
            profitMax = profitMax <= (prices[i] - minVal) ? (prices[i] - minVal) : profitMax;
            minVal = minVal >= prices[i] ? prices[i] : minVal;
            leftMax[i] = profitMax;
        }
        profitMax = 0;
        int maxVal = prices[prices.size()-1];
        for (int i = prices.size()-1;i >= 0;i--) {
            profitMax = profitMax <= (maxVal - prices[i]) ? (maxVal - prices[i]) : profitMax;
            maxVal = maxVal <= prices[i] ? prices[i] : maxVal;
            rightMax[i] = profitMax;
        }
        
        int finalMaxProfit = 0;
        for (int k=0;k<prices.size();k++) {
            finalMaxProfit = finalMaxProfit <= (leftMax[k] + rightMax[k]) ? (leftMax[k] + rightMax[k]) : finalMaxProfit;
        }
        
        return finalMaxProfit;
    }
};