2025-11-20：买卖股票的最佳时机Ⅴ。用go语言，给定一个整数数组 prices（prices[i] 表示第 i 天的股票

2025-11-20：买卖股票的最佳时机Ⅴ。用go语言，给定一个整数数组 prices（prices[i] 表示第 i 天的股票价格），以及一个整数 k。你最多可以执行 k 笔交易，每笔交易有两种形式：

• • 正向交易（先买后卖）：在某天 i 买入，在之后的某天 j 卖出（i < j），该笔交易的收益为 prices[j] − prices[i]。

• • 做空交易（先卖后买回）：在某天 i 先卖出，之后在某天 j 买回（i < j），该笔交易的收益为 prices[i] − prices[j]。
  约束条件：

• • 每次交易必须在前一笔交易完成后才能开始，交易之间不能重叠；

• • 同一天内不能同时进行买入和卖出操作。

目标是在不超过 k 笔交易的前提下，使总收益最大化，返回该最大可能的累计收益。

2 <= prices.length <= 1000。

1 <= prices[i] <= 1000000000。

1 <= k <= prices.length / 2。

输入: prices = [12,16,19,19,8,1,19,13,9], k = 3。

输出: 36。

解释:

我们可以通过 3 笔交易获得 36 美元的利润：

• • 一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。

• • 一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。

• • 一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。

题目来自力扣3573。

程序过程详细描述

1. 1.状态定义：

• • 程序使用一个二维数组f，其维度为(k+2) x 3。其中：

• • •f[j][0]表示在完成最多j笔交易后，当前处于“空闲状态”（不持有任何头寸）时的最大收益。

  • •f[j][1]表示在完成最多j笔交易后，当前持有“多头头寸”（已买入股票但未卖出）时的最大收益。

  • •f[j][2]表示在完成最多j笔交易后，当前持有“空头头寸”（已卖空股票但未买回）时的最大收益。

• • 索引j的范围是0到k+1，其中j=0表示未进行任何交易，j=k+1是为了覆盖最多k笔交易的边界情况。

2.初始化：

• • 将f数组的初始值设置为一个极小的负数（math.MinInt / 2），表示不可能状态或未初始化状态。

• • 特别地，f[0][0]也被初始化为极小负数，但实际初始状态（0笔交易、空闲状态）的收益应为0，不过程序通过后续更新覆盖此值。

3.遍历价格数组：

• • 对于每一天的价格p，程序逆序更新j从k+1到1（逆序是为了避免状态覆盖，确保使用前一天的数据）。

• • 对于每个j，更新三个状态：

• • •更新空闲状态（f[j][0]）：

  • • • 可能来自三种情况：

    • • • 保持空闲：f[j][0]自身。

      • • 从多头头寸平仓：卖出持有的股票，收益增加p，即f[j][1] + p。这完成了一笔正向交易（但交易次数j不变，因为交易次数在开仓时已计算）。

      • • 从空头头寸平仓：买回股票平仓，收益减少p，即f[j][2] - p。这完成了一笔做空交易。

    • • 取这三种情况的最大值。

  • •更新多头头寸状态（f[j][1]）：

  • • • 可能来自两种情况：

    • • • 保持多头头寸：f[j][1]自身。

      • • 从空闲状态开仓买入：在空闲状态下买入股票，开始新交易。收益减少p，并从j-1笔交易的状态转移，即f[j-1][0] - p。这里j-1到j表示开仓操作占用了一笔交易次数。

  • •更新空头头寸状态（f[j][2]）：

  • • • 类似地，可能来自：

    • • • 保持空头头寸：f[j][2]自身。

      • • 从空闲状态开仓做空：在空闲状态下卖出股票（做空），开始新交易。收益增加p，即f[j-1][0] + p，交易次数从j-1增加到j。

4.状态转移的核心：

• • 开仓操作（买入或做空）会增加交易次数j，并从空闲状态转移。

• • 平仓操作（卖出或买回）不改变j，但将头寸转为空闲状态。

• • 交易不能重叠，因此任何时候最多持有一个头寸（多头或空头）。

5.返回结果：

• • 遍历所有价格后，返回f[k+1][0]，表示在最多进行k笔交易后处于空闲状态的最大收益。这里使用k+1是为了确保覆盖所有交易次数，因为初始化时j从0开始。

• •时间复杂度：程序需要遍历价格数组中的每个价格（长度为n），对于每个价格，逆序遍历j从k+1到1（共k次循环）。因此，总时间复杂度为O(n × k)。

• •空间复杂度：程序维护了一个二维数组f，大小为(k+2) × 3。由于k是输入参数且k ≤ n/2，额外空间复杂度为O(k)（与n无关，但受k限制）。

该动态规划方法通过状态机模型高效处理了两种交易类型，确保了在约束下最大化收益。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func maximumProfit(prices []int, k int)int64 {
    f := make([][3]int, k+2)
    for j := 1; j <= k+1; j++ {
        f[j][1] = math.MinInt / 2
        f[j][2] = math.MinInt / 2
    }
    f[0][0] = math.MinInt / 2
    for _, p := range prices {
        for j := k + 1; j > 0; j-- {
            f[j][0] = max(f[j][0], f[j][1]+p, f[j][2]-p)
            f[j][1] = max(f[j][1], f[j-1][0]-p)
            f[j][2] = max(f[j][2], f[j-1][0]+p)
        }
    }
    returnint64(f[k+1][0])
}

 func main() {
    prices := []int{12, 16, 19, 19, 8, 1, 19, 13, 9}
    k := 3
    result := maximumProfit(prices, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import math

 def maximumProfit(prices, k):
    # 初始化动态规划数组
    # f[j][0]: 空仓状态的最大利润
    # f[j][1]: 持有第一支股票状态的最大利润  
    # f[j][2]: 持有第二支股票状态的最大利润
    f = [[0] * 3for _ in range(k + 2)]
    # 初始化状态
    for j in range(1, k + 2):
        f[j][1] = -10**18  # 使用一个很大的负数代替math.MinInt
        f[j][2] = -10**18
    f[0][0] = -10**18
    # 动态规划处理每个价格
    for p in prices:
        # 从后往前更新，避免状态覆盖
        for j in range(k + 1, 0, -1):
            # 更新空仓状态：保持空仓、卖出第一支、卖出第二支
            f[j][0] = max(f[j][0], f[j][1] + p, f[j][2] - p)
            # 更新持有第一支股票状态：保持持有、从空仓买入
            f[j][1] = max(f[j][1], f[j-1][0] - p)
            # 更新持有第二支股票状态：保持持有、从空仓买入
            f[j][2] = max(f[j][2], f[j-1][0] + p)
    return f[k+1][0]

 # 测试代码
if __name__ == "__main__":
    prices = [12, 16, 19, 19, 8, 1, 19, 13, 9]
    k = 3
    result = maximumProfit(prices, k)
    print(result) 

C++完整代码如下：

  

  

  

  


 using namespace std;

 long long maximumProfit(vector& prices, int k) {
    // 初始化动态规划数组
    // f[j][0]: 空仓状态的最大利润
    // f[j][1]: 持有第一支股票状态的最大利润
    // f[j][2]: 持有第二支股票状态的最大利润
    vector 
 
 > f(k +  
 2, vector 
 
 ( 
 3));

     // 初始化状态
    for (int j = 1; j <= k + 1; j++) {
        f[j][1] = LLONG_MIN / 2;  // 使用long long的最小值
        f[j][2] = LLONG_MIN / 2;
    }
    f[0][0] = LLONG_MIN / 2;

     // 动态规划处理每个价格
    for (int p : prices) {
        // 从后往前更新，避免状态覆盖
        for (int j = k + 1; j > 0; j--) {
            // 更新空仓状态：保持空仓、卖出第一支、卖出第二支
            f[j][0] = max({f[j][0], f[j][1] + p, f[j][2] - p});
            // 更新持有第一支股票状态：保持持有、从空仓买入
            f[j][1] = max(f[j][1], f[j-1][0] - p);
            // 更新持有第二支股票状态：保持持有、从空仓买入
            f[j][2] = max(f[j][2], f[j-1][0] + p);
        }
    }

     return f[k+1][0];
}

 int main() {
    vector prices = {12, 16, 19, 19, 8, 1, 19, 13, 9};
    int k = 3;
    long long result = maximumProfit(prices, k);
    cout << result << endl;  // 输出结果

     return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。