解题思路

• 本题等价于经典问题“最多进行 k 次买卖的最大利润”。

• 若 k >= n/2（天数的一半），约束形同无约束：可以把所有上升幅度相加（贪心：把每个相邻正差累加）。

• 否则使用动态规划的“交易次数 × 持有状态”转移，滚动优化到一维：

  • 定义：

    • buy[j]：完成 j 次卖出后、再买入并持有的最大收益（第 j+1 笔正在持有），
    • sell[j]：完成 j 次卖出的最大收益（手上无货）。

  • 转移（遍历每天价格 p，j = 1..k）：

    • buy[j] = max(buy[j], sell[j-1] - p)（用上一次的卖出继续买）
    • sell[j] = max(sell[j], buy[j] + p) （把当前持有卖掉）

  • 初值：sell[0]=0，buy[j] = -∞（表示还不可能持有），答案为 sell[k]。

复杂度分析

• 时间复杂度：O(nk)（当 k < n/2），极端 k >= n/2 时为 O(n)。
• 空间复杂度：O(k)（只需两条长度为 k+1 的数组 buy/sell）。

代码实现

Python

# 题面功能写在外部函数里
from ast import literal_eval
import sys

def max_profit_k_transactions(prices, k):
    n = len(prices)
    if n == 0 or k == 0:
        return 0
    # 当k足够大时，等价于不限次：累加所有上升段
    if k >= n // 2:
        ans = 0
        for i in range(1, n):
            if prices[i] > prices[i-1]:
                ans += prices[i] - prices[i-1]
        return ans
    # DP：O(k) 空间
    INF_NEG = -10**18
    buy  = [INF_NEG] * (k + 1)  # buy[j]：已完成j次卖出后，持有
    sell = [0] * (k + 1)        # sell[j]：已完成j次卖出后，不持有
    for p in prices:
        for j in range(1, k + 1):
            # 注意先更新buy再更新sell不会冲突，因为sell[j-1]和buy[j]均来自上一时刻
            buy[j]  = max(buy[j],  sell[j-1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]

# 主函数：读取输入并输出
def main():
    line = sys.stdin.readline().strip()
    # 解析格式如: "[7,1,5,3,6,4],2"
    # Python优先使用literal_eval处理数组部分
    lb = line.find('[')
    rb = line.rfind(']')
    prices_str = line[lb:rb+1]
    k_str = line[rb+2:] if rb+2 <= len(line) else "0"
    prices = literal_eval(prices_str)
    k = int(k_str.strip().split()[0])
    print(max_profit_k_transactions(prices, k))

if __name__ == "__main__":
    main()

Java

// 类名统一为 Main；ACM 风格：从标准输入读写
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    // 题面功能写在外部函数里
    public static int maxProfitKTransactions(int[] prices, int k) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        // k 很大时转为不限次
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
            }
            return ans;
        }
        // DP：O(k) 空间
        final int INF_NEG = (int)-1e9; // 足够小
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        for (int j = 0; j <= k; j++) {
            buy[j] = INF_NEG; // 初始不可持有
            sell[j] = 0;
        }
        for (int p : prices) {
            for (int j = 1; j <= k; j++) {
                // 先更新buy[j]再更新sell[j]，逻辑上来自前一日状态
                if (sell[j - 1] - p > buy[j]) buy[j] = sell[j - 1] - p;
                if (buy[j] + p > sell[j]) sell[j] = buy[j] + p;
            }
        }
        return sell[k];
    }

    // 主函数：读取输入并输出
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine().trim(); // 形如: "[7,1,5,3,6,4],2"
        int lb = line.indexOf('[');
        int rb = line.lastIndexOf(']');
        String arr = line.substring(lb + 1, rb).replace(" ", "");
        String kPart = line.substring(rb + 1);
        // 解析 prices
        String[] parts = arr.length() == 0 ? new String[0] : arr.split(",");
        int[] prices = new int[parts.length];
        for (int i = 0; i < parts.length; i++) prices[i] = Integer.parseInt(parts[i]);
        // 解析 k（跳过逗号与空格）
        kPart = kPart.replace(",", " ").trim();
        int k = Integer.parseInt(kPart.split("\\s+")[0]);
        System.out.println(maxProfitKTransactions(prices, k));
    }
}

C++

// ACM 风格：从标准输入读写
#include <bits/stdc++.h>
using namespace std;

// 题面功能写在外部函数里
int maxProfitKTransactions(const vector<int>& prices, int k) {
    int n = (int)prices.size();
    if (n == 0 || k == 0) return 0;
    // k 很大时转为不限次
    if (k >= n / 2) {
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (prices[i] > prices[i - 1]) ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
    const long long INF_NEG = (long long)-4e18;
    vector<long long> buy(k + 1, INF_NEG), sell(k + 1, 0);
    for (int p : prices) {
        for (int j = 1; j <= k; ++j) {
            // buy[j]: 完成j次卖出后持有
            buy[j]  = max(buy[j], sell[j - 1] - (long long)p);
            // sell[j]: 完成j次卖出后空仓
            sell[j] = max(sell[j], buy[j] + (long long)p);
        }
    }
    return (int)sell[k];
}

// 主函数：读取输入并输出
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    if (!getline(cin, line)) return 0;  // 输入形如: "[7,1,5,3,6,4],2"
    // 提取数组与k
    int lb = line.find('['), rb = line.rfind(']');
    string arr = (lb == string::npos || rb == string::npos || rb < lb) ? "" : line.substr(lb + 1, rb - lb - 1);
    string kPart = rb + 1 < (int)line.size() ? line.substr(rb + 1) : "";
    // 解析 prices：用替换字符+输入流
    for (char& c : arr) if (c == ',') c = ' ';
    stringstream ss(arr);
    vector<int> prices;
    int x;
    while (ss >> x) prices.push_back(x);
    // 解析 k
    for (char& c : kPart) if (c == ',' ) c = ' ';
    stringstream sk(kPart);
    int k = 0; sk >> k;
    cout << maxProfitKTransactions(prices, k) << "\n";
    return 0;
}

题目内容

你是某著名 $IP$ 毛绒公仔的收藏家，手上有一张该公仔的价目表 $prices$ 。其中 $prices[i]$ 日是第 $i$ 天每箱公仔的价格、共 $n$ 天。

由于公平交易规制、规则如下:

• 你每天最多只能存货 $1$ 箱。

• 最多可以进行 $k$ 笔交易(买入 $k$ 次、卖出 $k$ 次)

目标:在 $n$ 天内任意买卖，求你能赚到的最大差价利润。

样例1

输入

[7,1,5,3,6,4],2

输出

7

说明

在第 $2$ 天(公仔价格 $=1$ )的时候买入，在第 $3$ 天(公仔价格 $=5$ )的时候卖出，这笔交易所能获得利润 $=5-1=4$ 。

随后，在第 $4$ 天(公仔价格 $=3$ )的时候买入，在第 $5$ 天(公仔价格 $=6$ )的时候卖出,这笔交易所能获得利润 $=6-3=3$ 。

样例2

输入

[8,6,5,3,3],2

输出

0

说明

交易一直无法获得正利润，不交易最终利润最大为 $0$