买卖股票的最好时机(三)

C++ 解法, 执行用时: 13ms, 内存消耗: 3212KB, 提交时间: 2022-06-30

static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        vector<int> first(prices.size(), 0);
        int minp = prices[0];
        for(int i=1; i<prices.size(); ++i){
            minp = min(minp, prices[i]);
            first[i] = max(first[i-1], prices[i]-minp);
        }
        vector<int> second(prices.size(), 0);
        int maxp = prices[prices.size()-1];
        for(int i=prices.size()-2; i>=0; --i){
            maxp = max(maxp, prices[i]);
            second[i] = max(second[i+1], maxp-prices[i]);
        }
        int ans = 0;
        for(int i=0; i<prices.size(); ++i){
            ans = max(ans, first[i]+second[i]);
        }
        return ans;
    }
};

C++ 解法, 执行用时: 13ms, 内存消耗: 3220KB, 提交时间: 2022-05-29

static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();

        // buy1:  表示第i天交易完成后，买了第一只股票所获得的的最大利润
        // sell1: 表示第i天交易完成后，卖了第一只股票所获得的的最大利润
        // buy2:  表示第i天交易完成后，买了第二只股票所获得的的最大利润
        // sell2: 表示第i天交易完成后，卖了第二只股票所获得的的最大利润
        int buy1, sell1, buy2, sell2;
        int tmp_b1, tmp_s1, tmp_b2, tmp_s2;

        // base case
        tmp_b1 = buy1 = -prices[0];
        tmp_s1 = sell1 = 0;
        tmp_b2 = buy2 = -prices[0];
        tmp_s2 = sell2 = 0;

        /*
         * 状态转移方程：
         *   dp[i][0] = max(dp[i - 1][0], -prices[i])
         *   dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1])
         *   dp[i][2] = max(dp[i - 1][1] - prices[i], dp[i - 1][2])
         *   dp[i][3] = max(dp[i - 1][2] + prices[i], dp[i - 1][3])
         * */
        for (int i = 1; i < n; i++) {
            buy1 =  max(tmp_b1, -prices[i]);
            sell1 = max(tmp_s1, tmp_b1 + prices[i]);
            buy2 =  max(tmp_b2, tmp_s1 - prices[i]);
            sell2 = max(tmp_s2, tmp_b2 + prices[i]);
            tmp_b1 = buy1, tmp_s1 = sell1, tmp_b2 = buy2, tmp_s2 = sell2;
        }

        return sell2;
    }
};

C 解法, 执行用时: 15ms, 内存消耗: 3132KB, 提交时间: 2021-03-23

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @param pricesLen int prices数组长度
 * @return int整型
 */
#define max(a, b) ((a) > (b) ? (a) : (b))

int maxProfit(int* prices, int pricesLen ) {
    // write code here
    int dp1[pricesLen];  //1次买入
    int dp2[pricesLen];  //1次卖出
    int dp3[pricesLen];  //2次买入
    int dp4[pricesLen];  //2次卖出
    
    memset(dp1, 0, sizeof(int) * pricesLen);
    memset(dp2, 0, sizeof(int) * pricesLen);
    memset(dp3, 0, sizeof(int) * pricesLen);
    memset(dp4, 0, sizeof(int) * pricesLen);
    
    dp1[0] = -prices[0];
    dp2[0] = 0;
    dp3[0] = -prices[0];
    dp4[0] = 0;
    for (int i = 1; i < pricesLen; i++) {
        dp1[i] = max(dp1[i - 1], -prices[i]);
        dp2[i] = max(dp2[i - 1], dp1[i - 1] + prices[i]);
        dp3[i] = max(dp3[i - 1], dp2[i - 1] - prices[i]);
        dp4[i] = max(dp4[i - 1], dp3[i - 1] + prices[i]);
    }
    return max(dp2[pricesLen - 1], dp4[pricesLen - 1]);
}

C 解法, 执行用时: 15ms, 内存消耗: 3136KB, 提交时间: 2021-02-25

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @param pricesLen int prices数组长度
 * @return int整型
 */
int maxProfit(int* prices, int pricesLen ) {
    // write code here
    int first[pricesLen];
    int second[pricesLen];
    for(int i=0;i<pricesLen;i++)
    {
        first[i]=second[i]=0;
    }
    int max=prices[pricesLen-1];
    int min=prices[0];
    for(int i=1;i<pricesLen;i++)
    {
        if(min>prices[i])
            min=prices[i];
        if(prices[i]-min>first[i-1])
            first[i]=prices[i]-min;
        else
            first[i]=first[i-1];
    }
    for(int i=pricesLen-2;i>-1;i--)
    {
        if(max<prices[i])
            max=prices[i];
        if(max-prices[i]>second[i+1])
            second[i]=max-prices[i];
        else
            second[i]=second[i+1];
    }
    int sum=0;
    for(int i=0;i<pricesLen;i++)
    {
        if(sum<first[i]+second[i])
            sum=first[i]+second[i];
    }
    return sum;
}

C 解法, 执行用时: 15ms, 内存消耗: 3140KB, 提交时间: 2022-01-03

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @param pricesLen int prices数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int my_min(int lhs,int rhs)
{
    return lhs<rhs?lhs:rhs;
}
int my_max(int lhs,int rhs)
{
    return lhs>rhs? lhs:rhs;
}
int maxProfit(int* prices, int pricesLen ) {
    // write code here
    if(!prices||!pricesLen) 
        return 0;
    int buy_1 = prices[0],sell_1=0,buy_2 =0-prices[0],sell_2=0;
    for(int i = 1;i<pricesLen;i++)
    {
        int curPrice = prices[i];
        buy_1 = my_min(buy_1,curPrice);
        sell_1= my_max(sell_1, curPrice-buy_1);
        buy_2 = my_max(buy_2,sell_1-curPrice);
        sell_2 = my_max(sell_2,curPrice+buy_2);
        
    }
    return sell_2;
}

详情