2025-12-17 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 17

Description

Best Time to Buy and Sell Stock V

You are given an integer array prices where prices[i] is the price of a stock in dollars on the ith day, and an integer k.

You are allowed to make at most k transactions, where each transaction can be either of the following:

  • Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].

  • Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most k transactions.

 

Example 1:

Input: prices = [1,7,9,8,2], k = 2

Output: 14

Explanation:

We can make $14 of profit through 2 transactions:
  • A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
  • A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.

Example 2:

Input: prices = [12,16,19,19,8,1,19,13,9], k = 3

Output: 36

Explanation:

We can make $36 of profit through 3 transactions:
  • A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
  • A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
  • A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.

 

Constraints:

  • 2 <= prices.length <= 103
  • 1 <= prices[i] <= 109
  • 1 <= k <= prices.length / 2

Solution

class Solution {
public:
  long long maximumProfit(vector<int>& prices, int k) {
    int len = prices.size();
    vector<vector<vector<long long>>> dp(len, vector<vector<long long>>(k + 1, vector<long long>({0, -prices[0], prices[0]})));
    for(int i = 1; i < len; ++i) {
      int x = prices[i];
      for(int t = 1; t <= k; ++t) {
        long long profit = dp[i - 1][t][0];
        long long buy = dp[i - 1][t][1];
        long long sell = dp[i - 1][t][2];
        long long prevProfit = dp[i - 1][t - 1][0];
        profit = max({profit, buy + x, sell - x});
        buy = max(buy, prevProfit - x);
        sell = max(sell, prevProfit + x);
        dp[i][t][0] = profit;
        dp[i][t][1] = buy;
        dp[i][t][2] = sell;
      }
    }
    return dp[len - 1][k][0];
  }
};

// Accepted
// 776/776 cases passed (703 ms)
// Your runtime beats 37.53 % of cpp submissions
// Your memory usage beats 21.77 % of cpp submissions (344.9 MB)
Algorithm