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

``````class Solution {
public:
int maxProfit(int k, vector<int>& prices) {

// Step 1: Find out all profit opportunities
vector<int> profits;
stack<pair<int, int>> vps; // valley-peak pairs

int v;
int p = -1;
for (;;) {
// find next valley-peak pair
for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
for (p = v  ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);

if (v == p) { // v==p means that both v and p reach the end of the array
break;
}

// Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the new-found).
// If prices[v1] >= prices[v2],
// it is meaningless to combine the two transactions.
// Save of profit of (v1, p1), and pop it out of the record.
while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
vps.pop();
}

// If prices[v1]<prices[v2] and prices[p1]<prices[p2],
// then it is meaningful to combine the two transactions
// update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
profits.push_back(prices[vps.top().second] - prices[v]);
v = vps.top().first;
vps.pop();
}

// save the new-found valley-peak pair
vps.emplace(v, p);
}

// save all remaining profits
while (!vps.empty()) {
profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
vps.pop();
}

// Step 2: Calculate the k highest profits
int ret;
if (profits.size() <= k) {
ret = accumulate(profits.begin(), profits.end(), 0);
} else {
nth_element(profits.begin(), profits.end() - k, profits.end());
ret = accumulate(profits.end() - k, profits.end(), 0);
}
return ret;
}
};``````

• There is a follow-up, a.k.a. Maximum Subarray III:

Problem:
Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous. Every subarray should contain at least one number.
Return the largest sum.

Example: Given `[-1,4,-2,3,-2,3]`, `k=2`, return `8`

O(n) Solution:

This follow-up can be converted into "Best Time to Buy and Sell Stock IV" by simply calling the `partial_sum`.

``````class Solution {
public:
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
int maxSubArray(vector<int> nums, int k) {
if (count_if(nums.begin(), nums.end(), [](int x){return x>0;}) <= k) {
nth_element(nums.begin(), nums.end()-k, nums.end());
return accumulate(nums.end()-k, nums.end(), 0);
}
nums.insert(nums.begin(), 0);
partial_sum(nums.begin(), nums.end(), nums.begin());
return maxProfit(k, nums);
}

int maxProfit(int k, vector<int>& prices) {

// Step 1: Find out all profit opportunities
vector<int> profits;
stack<pair<int, int>> vps; // valley-peak pairs

int v;
int p = -1;
for (;;) {
// find next valley-peak pair
for (v = p+1; (v+1 < prices.size()) && (prices[v] >= prices[v+1]); ++v);
for (p = v  ; (p+1 < prices.size()) && (prices[p] <= prices[p+1]); ++p);

if (v == p) { // v==p means that both v and p reach the end of the array
break;
}

// Consider two transactions (v1, p1) (back of the stack) and (v2, p2) (the new-found).
// If prices[v1] >= prices[v2],
// it is meaningless to combine the two transactions.
// Save of profit of (v1, p1), and pop it out of the record.
while ((!vps.empty()) && (prices[v] <= prices[vps.top().first])) {
profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
vps.pop();
}

// If prices[v1]<prices[v2] and prices[p1]<prices[p2],
// then it is meaningful to combine the two transactions
// update (v1, p1) to (v1, p2), and save the profit of (v2, p1)
while ((!vps.empty()) && (prices[p] >= prices[vps.top().second])) {
profits.push_back(prices[vps.top().second] - prices[v]);
v = vps.top().first;
vps.pop();
}

// save the new-found valley-peak pair
vps.emplace(v, p);
}

// save all remaining profits
while (!vps.empty()) {
profits.push_back(prices[vps.top().second] - prices[vps.top().first]);
vps.pop();
}

// Step 2: Calculate the k highest profits
int ret;
if (profits.size() <= k) {
ret = accumulate(profits.begin(), profits.end(), 0);
} else {
nth_element(profits.begin(), profits.end() - k, profits.end());
ret = accumulate(profits.end() - k, profits.end(), 0);
}
return ret;
}

};
``````

• How can v2,p1 considered as a transaction opportunity. Because I think v2 always happens after p1.( we cannot sell stock before even buying them. ) Can you please explain?

• I think it's a tricky point. That means for Case 2, if we split (v1, p2) into (v1, p1) and (v2, p2), we can get (p1-v2) more profits but with one more transaction, equivalently there is a transaction with (p1-v2) profits. So it should be stored into profits and be compared in Step 2, what's more, it doesn't affect later v, p comparisons because p2 is the highest peak and v1 is the lowest valley for v1 to p2.

• thanks for the explain, but it take me quite sometime to figure out the trick.
the key point is: profit(v1, p2) + profit(v2, p1) = profit(v1, p1) + profit(v2, p2)

• @zhiqing_xiao This solution for the follow up is the best extension I've ever seen.

• Oh, clever to use nth to reduce the time complexity to O(n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.