Rust 解法, 执行用时: 9ms, 内存消耗: 3728KB, 提交时间: 2022-04-03

use std::io;

fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).expect("Failure");
    let n:i32 = n.trim().parse().expect("Failure");
    
    let mut prices = String::new();
    std::io::stdin().read_line(&mut prices).unwrap();
    let prices = prices.trim()
                .split_whitespace()
                .map(|s| s.parse::<i32>().unwrap())
                .collect::<Vec<i32>>();
    println!("{}", max_profit(prices));
}

fn max_profit(prices: Vec<i32>) -> i32 {
    let n  = prices.len();
    if n < 2 {
        return 0i32;
    }
    
    let mut dp = vec![[[0;2]; 3]; n];
    let num_transactions = 2;
    
    for i in 0..n {
        for j in (1..=num_transactions).rev() {
            if i == 0 {
                dp[i][j][1] = -prices[i];
            } else {
                dp[i][j][0] = dp[i-1][j][0].max(dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = dp[i-1][j][1].max(dp[i-1][j-1][0] - prices[i]);
            }
        }
    }
    
    dp[n-1][num_transactions][0]
}

C++ 解法, 执行用时: 13ms, 内存消耗: 812KB, 提交时间: 2022-03-14

#include <iostream>
#include <vector>

using namespace std;

class solution
{
public:
//     void getResult_Origin(vector<int> &nums)
//     {
//         int n = nums.size();
//         vector<vector<int>> dp(n, vector<int>(5, 0));
//         dp[0][1] = -nums[0];
//         dp[0][3] = -nums[0];
        
//         for (int i = 1; i < n; i++)
//         {
//             dp[i][0] = dp[i - 1][0];
//             dp[i][1] = max(dp[i - 1][0] - nums[i], dp[i - 1][1]);
//             dp[i][2] = max(dp[i - 1][1] + nums[i], dp[i - 1][2]);
//             dp[i][3] = max(dp[i - 1][2] - nums[i], dp[i - 1][3]);
//             dp[i][4] = max(dp[i - 1][3] + nums[i], dp[i - 1][4]);
//         }
        
//         cout << max(dp[n - 1][2], dp[n - 1][4]) << endl;
//     }
    
    void getResult_Optimize(vector<int> &nums)
    {
        int n = nums.size();
        
        int dp1 = -nums[0], dp2 = 0, dp3 = -nums[0], dp4 = 0;
        for (int i = 1; i < n; i++)
        {
            int t1 = max(- nums[i], dp1);
            int t2 = max(dp1 + nums[i], dp2);
            int t3 = max(dp2 - nums[i], dp3);
            dp4 = max(dp3 + nums[i], dp4);
            dp3 = t3, dp2 = t2, dp1 = t1;
        }
        
        cout << max(dp2, dp4) << endl;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    
    // solution().getResult_Origin(nums);
    solution().getResult_Optimize(nums);
    
    return 0;
}

C++ 解法, 执行用时: 13ms, 内存消耗: 2768KB, 提交时间: 2022-04-22

#include<iostream>
#include<algorithm>
using namespace std;
int price[100000],dp[200005][5] = {0};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0;i < n;++i)
        cin >> price[i];
    dp[0][1] = -price[0];
    dp[0][3] = -price[0];
    for(int i = 1;i < n;++i){
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] - price[i]);
        dp[i][2] = max(dp[i - 1][2],dp[i - 1][1] + price[i]);
        dp[i][3] = max(dp[i - 1][3],dp[i - 1][2] - price[i]);
        dp[i][4] = max(dp[i - 1][4],dp[i - 1][3] + price[i]);
    }
    cout << dp[n - 1][4];
    return 0;
}

C++ 解法, 执行用时: 14ms, 内存消耗: 780KB, 提交时间: 2022-03-19

#include <cstdio>
#include <vector>
#include <limits.h>

int main() {
    int n; 
    scanf("%d", &n);
    std::vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &prices[i]);
    }
//     int fhold = -prices[0], fsell = 0, shold = -prices[0], ssell = 0;
//     for (int price : prices) {
//         // 第二次买卖，类似于进行多笔交易的思想
//         // 第二次卖
//         ssell = std::max(ssell, shold + price);
//         // 第二次买，必须是第一次卖掉后
//         shold = std::max(shold, fsell - price);
        
//         // 第一次买卖，类似于只能进行一笔交易
//         // 第一次卖
//         fsell = std::max(fsell, fhold + price);
//         // 第一次买
//         fhold = std::max(fhold, -price);
//     }
//     printf("%d\n", ssell);
    std::vector<std::vector<int>> dp(3, std::vector<int>(2));
    dp[0][0] = 0;
    dp[0][1] = INT_MIN;
    for (int i = 1; i <= 2; ++i) {
        dp[i][0] = 0;
        dp[i][1] = -prices[0];
    }
    for (int i = 0; i < n; ++i) {
        // 不持有
        for (int j = 2; j >= 1; --j) {
            dp[j][0] = std::max(dp[j][0], dp[j][1] + prices[i]);
            dp[j][1] = std::max(dp[j][1], dp[j - 1][0] - prices[i]);
        }
    }
    printf("%d\n", dp[2][0]);
    return 0;
}

C++ 解法, 执行用时: 15ms, 内存消耗: 780KB, 提交时间: 2022-05-30

#include<iostream>
#include<algorithm>
using namespace std;
int price[100000], dp[200005][5] = { 0 };
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,buy1 = 0,sale1 = 0,buy2 = 0,sale2 = 0;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> price[i];
    buy1 = -price[0];
    buy2 = -price[1];
    for (int i = 1; i < n; ++i) {
        buy1 = max(buy1, - price[i]);
        sale1 = max(sale1, buy1 + price[i]);
        buy2 = max(buy2, sale1 - price[i]);
        sale2 = max(sale2, buy2 + price[i]);
    }
    cout << sale2;
}