Best time to buy and sell stock II
Expedia
ZetaThe problem
Given an array arr of n integers, where arr[i] represents price of the stock on the ith day. Determine the maximum profit achievable by buying and selling the stock any number of times.
Holding **at most **one share of the stock at any given time is allowed, meaning buying and selling the stock can be done any number of times, but the stock must be sold before buying it again. Buying and selling the stock on the same day is permitted.
Input: arr = [9, 2, 6, 4, 7, 3] **Output: **7 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6 - 2 = 4. Then buy on day 4 (price = 4) and sell on day 5 (price = 7), profit = 7 - 4 = 3. Total profit is 4 + 3 = 7.
Input: arr = [2, 3, 4, 5, 6] Output: 4 Explanation: Buy on day 1 (price = 2) and sell on day 5 (price = 6), profit = 6 - 2 = 4. Total profit is 4.
Input: arr = [8, 6, 5, 4, 3]
- 1 <= n<= 105
- 0 <= arr[i] <= 104
cpp
class Solution{
public:
int stockBuySell(vector<int> arr, int n){
}
};java
class Solution {
public int stockBuySell(int[] arr, int n) {
}
}python
class Solution:
def stockBuySell(self, arr, n):javascript
class Solution {
stockBuySell(arr, n) {
}
}csharp
class Solution
{
public int StockBuySell(int[] arr, int n)
{
}
}go
func stockBuySell(arr []int, n int) int {
}Stuck? Show a way to structure it+
- 01Inspect every adjacent day-to-day price change.
- 02Add each positive increase to total profit.
- 03Explain how consecutive gains combine into the same valley-to-peak transaction.
- 04Skip non-positive adjacent changes because they cannot improve total profit.
Reference answer
Then expect these follow-ups
How does a transaction fee change the solution?
Tests: DP variant
How would you output the valley-to-peak transactions?
Tests: reconstruction
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question