专栏首页Reck ZhangLeetCode 0188 - Best Time to Buy and Sell Stock IV

LeetCode 0188 - Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV

Desicription

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).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Solution

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        priority_queue<int> profits;
        stack<pair<int, int>> vps;
        int v = 0;
        int p = 0;
        int len = prices.size();
        while(p < len) {
            for(v = p; v < len-1 && prices[v] >= prices[v+1]; v++);
            for(p = v+1; p < len && prices[p] >= prices[p-1]; p++);
            while(vps.size() && prices[vps.top().first] > prices[v]) {
                profits.push(prices[vps.top().second - 1] - prices[vps.top().first]);
                vps.pop();
            }
            while(vps.size() && prices[vps.top().second-1] <= prices[p-1]) {
                profits.push(prices[vps.top().second-1] - prices[v]);
                v = vps.top().first;
                vps.pop();
            }
            vps.push(pair<int, int>(v, p));
        }
        while(vps.size()) {
            profits.push(prices[vps.top().second-1] - prices[vps.top().first]);
            vps.pop();
        }
        int res = 0;
        while(k-- && profits.size())
            res += profits.top(), profits.pop();
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 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 o...

    triplebee
  • Array - 188. Best Time to Buy and Sell Stock IV

    Say you have an array for which the _i_th element is the price of a given stock ...

    用户5705150
  • 【leetcode】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...

    阳光岛主
  • Leetcode: Best Time to Buy and Sell Stock

    题目: Say you have an array for which the ith element is the price of a given st...

    卡尔曼和玻尔兹曼谁曼
  • 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...

    ShenduCC
  • 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 o...

    triplebee
  • 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...

    chenjx85
  • Leetcode 121. Best Time to Buy and Sell Stock

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 【leetcode】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...

    阳光岛主
  • 【leetcode】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...

    阳光岛主
  • leetcode: 121. Best Time to Buy and Sell Stock

    JNingWei
  • Leetcode: Best Time to Buy and Sell Stock II

    题目: Say you have an array for which the ith element is the price of a given st...

    卡尔曼和玻尔兹曼谁曼
  • LeetCode 0121 - 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...

    Reck Zhang
  • 【leetcode系列】121. 买卖股票的最佳时机

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

    lucifer210
  • 一个函数解决【LeetCode 买卖股票的最佳时机】系列所有题目!

    之前介绍了【LeetCode 买卖股票的最佳时机】系列一共六道题目,这里把之前的题解还有题目链接汇总一下,方便大家查找。

    lucifer210
  • LeetCode 188. Best Time to Buy and Sell Stock IV (动态规划)

    题意:给你一个数组代表每天的股价。你有k次买入和卖出的机会,问你最多能赚多少钱。买入之前必须卖出已有股份。同一天是可以先买,再卖,或者先卖再买的。

    ShenduCC
  • 【leetcode系列】122. 买卖股票的最佳时机 II

    lucifer210
  • LeetCode 122. Best Time to Buy and Sell Stock II

    题目:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/

    ShenduCC
  • LeetCode 123. Best Time to Buy and Sell Stock III

    https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

    ShenduCC

扫码关注云+社区

领取腾讯云代金券