3573. Best Time to Buy and Sell Stock V Medium

1/**
2 * [3573] Best Time to Buy and Sell Stock V
3 *
4 * You are given an integer array prices where prices[i] is the price of a stock in dollars on the i^th day, and an integer k.
5 * You are allowed to make at most k transactions, where each transaction can be either of the following:
6 * 
7 * 	
8 * 	Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].
9 * 	
10 * 	
11 * 	Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].
12 * 	
13 * 
14 * 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.
15 * Return the maximum total profit you can earn by making at most k transactions.
16 *  
17 * <strong class="example">Example 1:
18 * <div class="example-block">
19 * Input: <span class="example-io">prices = [1,7,9,8,2], k = 2</span>
20 * Output: <span class="example-io">14</span>
21 * Explanation:
22 * We can make $14 of profit through 2 transactions:
23 * 
24 * 	A normal transaction: buy the stock on day 0 for $1 then sell it on day 2 for $9.
25 * 	A short selling transaction: sell the stock on day 3 for $8 then buy back on day 4 for $2.
26 * </div>
27 * <strong class="example">Example 2:
28 * <div class="example-block">
29 * Input: <span class="example-io">prices = [12,16,19,19,8,1,19,13,9], k = 3</span>
30 * Output: <span class="example-io">36</span>
31 * Explanation:
32 * We can make $36 of profit through 3 transactions:
33 * 
34 * 	A normal transaction: buy the stock on day 0 for $12 then sell it on day 2 for $19.
35 * 	A short selling transaction: sell the stock on day 3 for $19 then buy back on day 4 for $8.
36 * 	A normal transaction: buy the stock on day 5 for $1 then sell it on day 6 for $19.
37 * </div>
38 *  
39 * Constraints:
40 * 
41 * 	2 <= prices.length <= 10^3
42 * 	1 <= prices[i] <= 10^9
43 * 	1 <= k <= prices.length / 2
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-v/
49// discuss: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-v/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn maximum_profit(prices: Vec<i32>, k: i32) -> i64 {
55        
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_3573() {
67    }
68}
69