188. 买卖股票的最佳时机 IV (每日一题)

lzyprime 博客 (github)
创建时间：2020.12.28
qq及邮箱：2383518170

leetcode 笔记

---

题目描述

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 

提示：
0 <= k <= 10^9
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

code

• c++

class Solution
{
public:
    int maxProfit(int k, vector<int> &prices)
    {
        int size = prices.size();
        if (size < 2 || k == 0)
            return 0;

        k = min(k, size / 2);
        vector<int> b(k + 1, -1000), s(k + 1, 0);
        
        for (int v : prices)
            for (int j = 1; j <= k; ++j)
            {
                b[j] = max(b[j], s[j - 1] - v);
                s[j] = max(s[j], b[j] + v);
            }
        return s.back();
    }
};

拆解：

// 最多可做的交易数
k = min(k, size / 2);

for (int v : prices){

    // i - 1天过后，每笔交易完成后的最优解
    vector<int> pre = s;

    for (int j = 1; j <= k; ++j)
    {
        // b[j] 存第 j 笔交易买入后的结果
        // 所以如果买第i天的股票。则可获得的金额为: 当前第j - 1笔交易完成后的结果pre[j - 1] - 股票价格
        // 与当前的购买方案比较留下最优解。
        // 由于此时s[j - 1]并没有任何修改，pre[j - 1] == s[j - 1]
        b[j] = max(b[j], pre[j - 1] - v);

        // s[j] 存第 j 笔交易完成时的结果
        // 如果按第 i 天价格卖出，则可获得的金额为: 当前第j笔交易买入后的结果b[j] + 股票价格
        // 与当前卖出方案留最优解。
        // 同上，由于此时s[j]并没有任何修改，pre[j] == s[j], 所以pre数组可以免掉
        s[j] = max(pre[j], b[j] + v);
    }
}

• kotlin

一刀流，没意义。 涉及下标访问的，函数式都差点意思。

fun maxProfit(k: Int, prices: IntArray): Int = prices.fold(Array(min(k, prices.size / 2) + 1) { -1000 to 0 }) { arr, v -> arr.apply { (1..arr.lastIndex).forEach { i -> arr[i] = max(arr[i].first, arr[i - 1].second - v) to max(arr[i].second, arr[i].first + v) } } }.last().second

import kotlin.math.min
import kotlin.math.max

class Solution {
    fun maxProfit(k: Int, prices: IntArray): Int = prices.fold(
        Array(
            min(
                k,
                prices.size / 2
            ) + 1
        ) { -1000 to 0 }) { arr, v ->
        arr.apply {
            (1..arr.lastIndex).forEach { i ->
                arr[i] = max(arr[i].first, arr[i - 1].second - v) to max(arr[i].second, arr[i].first + v)
            }
        }
    }.last().second
}

• scala

一刀流

def maxProfit(k: Int, prices: Array[Int]): Int = prices.foldLeft(Array.fill(math.min(k, prices.length / 2) + 1)(-1000 -> 0)) { (acc, v) => (1 until acc.length).foreach(i => acc(i) = math.max(acc(i)._1, acc(i - 1)._2 - v) -> math.max(acc(i)._2, acc(i)._1 + v)); acc }.last._2

object Solution {
  def maxProfit(k: Int, prices: Array[Int]): Int =
    prices.foldLeft(Array.fill(math.min(k, prices.length / 2) + 1)(-1000 -> 0)) { (acc, v) =>
      (1 until acc.length).foreach(i =>
        acc(i) = math.max(acc(i)._1, acc(i - 1)._2 - v) -> math.max(acc(i)._2, acc(i)._1 + v))
      acc
    }.last._2
}

• rust

一刀流

pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {prices.iter().fold(vec![(-1000, 0); (k as usize).min(prices.len() / 2) + 1],|mut acc, v| {(1..acc.len()).for_each(|i| acc[i] = (acc[i].0.max(acc[i - 1].1 - v), acc[i].1.max(acc[i].0 + v)));acc},).last().unwrap().1}

impl Solution {
    pub fn max_profit(k: i32, prices: Vec<i32>) -> i32 {
        prices
            .iter()
            .fold(
                vec![(-1000, 0); (k as usize).min(prices.len() / 2) + 1],
                |mut acc, v| {
                    (1..acc.len()).for_each(|i| {
                        acc[i] = (acc[i].0.max(acc[i - 1].1 - v), acc[i].1.max(acc[i].0 + v))
                    });
                    acc
                },
            )
            .last()
            .unwrap()
            .1
    }
}