• 24.0%

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

### java

https://discuss.leetcode.com/topic/8984/a-concise-dp-solution-in-java

A Concise DP Solution in Java

The general idea is DP, while I had to add a “quickSolve” function to tackle some corner cases to avoid TLE.

DP: t(i,j) is the max profit for up to i transactions by time j (0<=i<=K, 0<=j<=T).

https://discuss.leetcode.com/topic/26169/clean-java-dp-solution-with-comment

Clean Java DP solution with comment

https://discuss.leetcode.com/topic/24079/easy-understanding-and-can-be-easily-modified-to-different-situations-java-solution

Easy understanding and can be easily modified to different situations Java Solution

The basic idea is to create two tables. hold and unhold.

hold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. hold means you have a stock in your hand.

unhold[i][j] means the maximum profit with at most j transaction for 0 to i-th day. unhold means you don’t have a stock in your hand.

The equation is

when you sell your stock this is a transaction but when you buy a stock, it is not considered as a full transaction. so this is why the two equation look a little different.

And we have to initiate hold table when k = 0.

When the situation is you can not buy a new stock at the same day when you sell it. For example you can only buy a new stock after one day you sell it. The same idea. Another situation is when you have to pay a transaction fee for each transaction, just make a modification when you sell it, So just change the unhold equation a little.

#### cpp

https://discuss.leetcode.com/topic/9522/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

C++ Solution with O(n + klgn) time using Max Heap and Stack

We can find all adjacent valley/peak pairs and calculate the profits easily. Instead of accumulating all these profits like Buy&Sell Stock II, we need the highest k ones.

The key point is when there are two v/p pairs (v1, p1) and (v2, p2), satisfying v1 <= v2 and p1 <= p2, we can either make one transaction at [v1, p2], or make two at both [v1, p1] and [v2, p2]. The trick is to treat [v1, p2] as the first transaction, and [v2, p1] as the second. Then we can guarantee the right max profits in both situations, p2 - v1 for one transaction and p1 - v1 + p2 - v2 for two.

Finding all v/p pairs and calculating the profits takes O(n) since there are up to n/2 such pairs. And extracting k maximums from the heap consumes another O(klgn).

https://discuss.leetcode.com/topic/12250/share-my-c-dp-solution-with-o-kn-time-o-k-space-10ms

Share my C++ DP solution with O(kn) time O(k) space, 10ms

This is my DP solution:

Inspired by weijiac in Best Time to Buy and Sell Stock III

https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1

https://discuss.leetcode.com/topic/30242/o-n-time-8ms-accepted-solution-with-detailed-explanation-c

O(n)-time 8ms Accepted Solution with Detailed Explanation (C++)

The idea of this thread was originally proposed by @yishiluo in

https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack

General idea:

We use the term “valley” to denote a local minimum index of prices, and the term “peak” to denote a local maximum index of prices. Let (v1, p1) and (v2, p2) denote two successive valley-peak pairs of the prices, respectively. Consider the two cases:

• Case 1: prices[v1] <= prices[v2] and prices[p1] <= prices[p2]. In this case, if we can conduct one transaction, we will use (v1, p2). If we can conduct two transactions, we will use (v1, p1) and (v2, p2). Equivalently, we can consider (v1, p2) as one transaction opportunity, and (v2, p1) as another transaction opportunity. The key idea is that these two original valley-peak pairs provide two transaction opportunities: (v1, p2) and (v2, p1).

• Case 2: prices[v1] >= prices[v2] or prices[p1] >= prices[p2]. In this case, if we can conduct one transaction, we will use either (v1, p1) or (v2, p2). If we can conduct two transactions, we will use both (v1, p1) and (v2, p2). That is, these two valley-peak pairs provides two transaction opportunities: (v1, p1) and (v2, p2).

The algorithm consists of two steps:

• Step 1: Find all transaction opportunities and record their profits. We use a stack vps to store the valley-peak pairs of the stock prices, wherein the valley value is sorted in ascending order. (The valley value at the top of the stack is the largest.) The profit of all transaction opportunities are recorded in the vector profits. The time complexity of this step is O(n).

• Step 2: Find the k most profitable transaction opportunities. The maximum profit we can get is the summation of the k opportunity. The time complexity of this step is O(n), too.

Overall complexity:

• Time: O(n)

• Space: worse-case O(n)

C++ code (Accepted 8ms)