C++实现LeetCode(188.买卖股票的最佳时间之四)

[LeetCode] 188.Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

这道题实际上是之前那道 Best Time to Buy and Sell Stock III 买股票的最佳时间之三的一般情况的推广，还是需要用动态规划Dynamic programming来解决，具体思路如下：

这里我们需要两个递推公式来分别更新两个变量local和global，我们其实可以求至少k次交易的最大利润。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：

local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)

global[i][j] = max(local[i][j], global[i - 1][j])，

其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值后相比，两者之中取较大值，而全局最优比较局部最优和前一天的全局最优。

但这道题还有个坑，就是如果k的值远大于prices的天数，比如k是好几百万，而prices的天数就为若干天的话，上面的DP解法就非常的没有效率，应该直接用Best Time to Buy and Sell Stock II 买股票的最佳时间之二的方法来求解，所以实际上这道题是之前的二和三的综合体，代码如下：

class Solution { public:     int maxProfit(int k, vector<int> &prices) {         if (prices.empty()) return 0;         if (k >= prices.size()) return solveMaxProfit(prices);         int g[k + 1] = {0};         int l[k + 1] = {0};         for (int i = 0; i < prices.size() - 1; ++i) {             int diff = prices[i + 1] - prices[i];             for (int j = k; j >= 1; --j) {                 l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);                 g[j] = max(g[j], l[j]);             }         }         return g[k];     }     int solveMaxProfit(vector<int> &prices) {         int res = 0;         for (int i = 1; i < prices.size(); ++i) {             if (prices[i] - prices[i - 1] > 0) {                 res += prices[i] - prices[i - 1];             }         }         return res;     } };

类似题目：

Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock

到此这篇关于C++实现LeetCode(188.买卖股票的最佳时间之四)的文章就介绍到这了,更多相关C++实现买卖股票的最佳时间之四内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(171.求Excel表列序号)

    [LeetCode] 171.Excel Sheet Column Number 求Excel表列序号 Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example:     A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -&g

  • C++实现LeetCode(186.翻转字符串中的单词之二)

    [LeetCode] 186. Reverse Words in a String II 翻转字符串中的单词之二 Given an input string , reverse the string word by word.  Example: Input:  ["t","h","e"," ","s","k","y"," ","i&qu

  • C++实现LeetCode(173.二叉搜索树迭代器)

    [LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++实现LeetCode(557.翻转字符串中的单词之三)

    [LeetCode] 557.Reverse Words in a String III 翻转字符串中的单词之三 Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1: Input: "Let's take LeetCode conte

  • C++实现LeetCode(172.求阶乘末尾零的个数)

    [LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数 Given an integer n, return the number of trailing zeroes in n!. Example 1: Input: 3 Output: 0 Explanation: 3! = 6, no trailing zero. Example 2: Input: 5 Output: 1 Explanation: 5! = 120, one trailing

  • C++实现LeetCode(169.求大多数)

    [LeetCode] 169. Majority Element 求大多数 Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1

  • C++实现LeetCode(179.最大组合数)

    [LeetCode] 179. Largest Number 最大组合数 Given a list of non negative integers, arrange them such that they form the largest number. Example 1: Input: [10,2] Output: "210" Example 2: Input: [3,30,34,5,9] Output: "9534330" Note: The result

  • C++实现LeetCode(188.买卖股票的最佳时间之四)

    [LeetCode] 188.Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You m

  • C++实现LeetCode(121.买卖股票的最佳时间)

    [LeetCode] 121.Best Time to Buy and Sell Stock 买卖股票的最佳时间 Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the sto

  • C++实现LeetCode(309.买股票的最佳时间含冷冻期)

    [LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as

  • C++实现LeetCode(122.买股票的最佳时间之二)

    [LeetCode] 122.Best Time to Buy and Sell Stock II 买股票的最佳时间之二 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie

  • python买卖股票的最佳时机（基于贪心/蛮力算法）

    python买卖股票的最佳时机（基于贪心/蛮力算法）

    开始刷leetcode算法题 今天做的是"买卖股票的最佳时机" 题目要求 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格. 设计一个算法来计算你所能获取的最大利润.你可以尽可能地完成更多的交易(多次买卖一支股票). 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票). 看到这个题目 最初的想法是蛮力法 通过两层循环 不断计算不同天之间的利润及利润和 下面上代码 class Solution(object): def maxProfit(self, pri

  • C++实现LeetCode(123.买股票的最佳时间之三)

    [LeetCode] 123.Best Time to Buy and Sell Stock III 买股票的最佳时间之三 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You

  • 基于java计算买卖股票的最佳时机

    基于java计算买卖股票的最佳时机

    这篇文章主要介绍了基于java计算买卖股票的最佳时机,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 问题: 可以将问题转化为如下图所示,即求多个累计的收入差 分析: 如果当前位置i的价格比i+1的价格高,则当前不是买入点,则继续判断下一个位置, 如果当前位置i的价格比i+1的价格低,并且i+1仍比i+1+1低,则在当前位置买入,知道i+n比i+n+1大时,卖出. 继续下一轮判断 package com.example.demo; public

  • C++ LeeCode题目:比特位计数和买卖股票的最佳时机

    C++ LeeCode题目:比特位计数和买卖股票的最佳时机

    目录 一.比特位计数 一.题目 二.代码 二.买卖股票的最佳时机 一.题目 二.代码 总结 一.比特位计数 一.题目 二.代码 十进制转二进制-百度百科 class Solution { public: vector<int> countBits(int n) { vector<int> num; for(int i=0;i<=n;i++){//遍历[0,n],计算每个值对应二进制1的个数 num.push_back(countOne(i)); } return num; }

  • Java通过动态规划设计股票买卖最佳时机

    Java通过动态规划设计股票买卖最佳时机

    目录 买卖股票的最佳时机 动态规划 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格.你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票.设计一个算法来计算你所能获取的最大利润.返回你可以从这笔交易中获取的最大利润.如果你不能获取任何利润,返回 0 . 示例: 链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock 动态规划

  • JavaScript股票的动态买卖规划实例分析下篇

    目录 1. 最佳买卖股票时机含冷冻期 题目描述 题解 2. 买卖股票的最佳时机 III 题目描述 题解 1. 最佳买卖股票时机含冷冻期 题目描述 给定一个整数数组prices,其中第prices[i]表示第i天的股票价格 . 设计一个算法计算出最大利润.在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天). 注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票). 示例 1: 输入: prices = [

随机推荐