# Best Time to Buy and Sell Stock II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii)
Canonical: https://scaleengineer.com/dsa/problems/best-time-to-buy-and-sell-stock-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Paytm](https://scaleengineer.com/companies/paytm), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [Nike](https://scaleengineer.com/companies/nike), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Media.net](https://scaleengineer.com/companies/media.net), [PhonePe](https://scaleengineer.com/companies/phonepe), [Geico](https://scaleengineer.com/companies/geico), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo), [Rakuten](https://scaleengineer.com/companies/rakuten), [Groww](https://scaleengineer.com/companies/groww), [CTC](https://scaleengineer.com/companies/ctc)
---
## Problem
You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` day.

On each day, you may decide to buy and/or sell the stock. You can only hold **at most one** share of the stock at any time. However, you can buy it then immediately sell it on the **same day**.

Find and return _the **maximum** profit you can achieve_.

**Example 1:**

**Input:** prices = [7,1,5,3,6,4]
**Output:** 7
**Explanation:** Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

**Example 2:**

**Input:** prices = [1,2,3,4,5]
**Output:** 4
**Explanation:** Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

**Example 3:**

**Input:** prices = [7,6,4,3,1]
**Output:** 0
**Explanation:** There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

**Constraints:**

* `1 <= prices.length <= 3 * 104`
* `0 <= prices[i] <= 104`

# Approaches
## Brute Force Recursion
This approach explores all possible transactions. For each day, we decide whether to buy, sell, or do nothing. This can be modeled using a recursive function that explores every possible sequence of actions.
**Time:** O(2^n) · **Space:** O(n)
**Pros:** Simple to conceptualize as it directly models the problem's decision process.
**Cons:** Extremely inefficient and will result in a "Time Limit Exceeded" error for larger inputs due to its exponential time complexity.
### Explanation
We define a recursive function, say `calculate(index, holding)`, which calculates the maximum profit from a given `index` in the `prices` array, with a boolean `holding` indicating whether we currently own a stock.

**Base Case**: If `index` reaches the end of the array, no more transactions can be made, so the profit is 0.

**Recursive Step**:
- If we are `holding` a stock: We can either sell it today for `prices[index]` and recursively call for the next day with `holding = false`, or we can hold it and recursively call for the next day with `holding = true`. We take the maximum profit from these two choices.
- If we are not `holding` a stock: We can either buy one today for `-prices[index]` and recursively call for the next day with `holding = true`, or we can skip buying and recursively call for the next day with `holding = false`. We take the maximum profit from these two choices.

The initial call to the function will be `calculate(0, false)`. This method explores a binary decision tree, leading to an exponential number of calls.

```java
class Solution {
    public int maxProfit(int[] prices) {
        return calculate(prices, 0, false);
    }

    private int calculate(int[] prices, int index, boolean holding) {
        if (index >= prices.length) {
            return 0;
        }

        // Option to do nothing and move to the next day
        int doNothingProfit = calculate(prices, index + 1, holding);

        int doSomethingProfit;
        if (holding) {
            // Option to sell
            doSomethingProfit = prices[index] + calculate(prices, index + 1, false);
        } else {
            // Option to buy
            doSomethingProfit = -prices[index] + calculate(prices, index + 1, true);
        }

        return Math.max(doNothingProfit, doSomethingProfit);
    }
}
```
### Algorithm
- Define a recursive function `calculate(prices, index, holding)`.
- Base Case: If `index >= prices.length`, return 0.
- If `holding` is true:
    - `sell_profit = prices[index] + calculate(prices, index + 1, false)`
    - `hold_profit = calculate(prices, index + 1, true)`
    - Return `max(sell_profit, hold_profit)`.
- If `holding` is false:
    - `buy_profit = -prices[index] + calculate(prices, index + 1, true)`
    - `skip_profit = calculate(prices, index + 1, false)`
    - Return `max(buy_profit, skip_profit)`.
- Start the process by calling `calculate(prices, 0, false)`.

## Dynamic Programming
This approach improves upon the brute-force method by using tabulation to avoid recomputing results for the same subproblems. We can define the state by the current day and whether we are holding a stock.
**Time:** O(n) · **Space:** O(n)
**Pros:** Much more efficient than brute force.; Provides a structured way to solve the problem that can be adapted to more complex stock trading scenarios.
**Cons:** Uses extra space proportional to the input size.; Can be further optimized to use constant space.
### Explanation
We can solve this problem using a bottom-up dynamic programming approach. We'll create a 2D DP table, `dp[n][2]`, where `n` is the number of days.

- `dp[i][0]` will store the maximum profit achievable at the end of day `i` if we are not holding any stock.
- `dp[i][1]` will store the maximum profit achievable at the end of day `i` if we are holding one share of the stock.

**State Transition Equations**:
- To have no stock on day `i` (`dp[i][0]`): We either had no stock on day `i-1` and did nothing, or we held a stock on day `i-1` and sold it on day `i`.
  `dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])`
- To hold a stock on day `i` (`dp[i][1]`): We either held a stock on day `i-1` and did nothing, or we had no stock on day `i-1` and bought one on day `i`.
  `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`

**Base Cases**:
- On day 0, if we don't buy, the profit is 0: `dp[0][0] = 0`.
- On day 0, if we buy, the profit is `-prices[0]`: `dp[0][1] = -prices[0]`.

We iterate from day 1 to `n-1`, filling the DP table. The final answer is `dp[n-1][0]`, as we must sell all stocks by the last day to maximize profit.

```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int n = prices.length;
        int[][] dp = new int[n][2];

        // dp[i][0]: max profit on day i with no stock
        // dp[i][1]: max profit on day i with one stock

        // Base case
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            // Max profit with no stock today:
            // 1. Had no stock yesterday, do nothing.
            // 2. Had stock yesterday, sell it today.
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);

            // Max profit with stock today:
            // 1. Had stock yesterday, do nothing.
            // 2. Had no stock yesterday, buy it today.
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }
}
```
### Algorithm
- If `prices` has 0 or 1 element, return 0.
- Create a DP table `dp[n][2]`.
- Initialize base cases: `dp[0][0] = 0` and `dp[0][1] = -prices[0]`.
- Iterate from `i = 1` to `n-1`:
    - `dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])`
    - `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`
- Return `dp[n-1][0]`.

## Greedy Approach (Peak Valley)
This is the most efficient and intuitive approach. The key insight is that the total profit from a series of transactions is the sum of profits from individual, consecutive upward price movements. We can simply accumulate all positive gains from one day to the next.
**Time:** O(n) · **Space:** O(1)
**Pros:** Highly efficient with linear time and constant space.; The logic is simple and easy to implement.
**Cons:** This specific greedy strategy works because of the problem's allowance for unlimited transactions. It might not be applicable to other stock problems with more constraints (e.g., transaction fees, cooldown periods).
### Explanation
The problem allows us to buy and sell on the same day. This flexibility means we don't have to worry about finding the absolute lowest valley and highest peak over a long period. Instead, we can focus on short-term gains.

Consider a price sequence `a, b, c`. The profit from buying at `a` and selling at `c` is `c - a`. This is mathematically equivalent to `(b - a) + (c - b)`. This implies that we can decompose a single large profitable transaction into a series of smaller, day-to-day profitable transactions.

Therefore, the strategy is to iterate through the prices and whenever we see an increase from day `i-1` to day `i` (i.e., `prices[i] > prices[i-1]`), we "transact" and add the profit `prices[i] - prices[i-1]` to our total.

This is a greedy approach because at each step, we make the locally optimal choice of taking any available profit, and this leads to the globally optimal solution. This approach is also equivalent to a space-optimized version of the dynamic programming solution.

```java
class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                maxProfit += prices[i] - prices[i-1];
            }
        }
        return maxProfit;
    }
}
```
### Algorithm
- Initialize `maxProfit = 0`.
- Iterate through the `prices` array from the second element (`i = 1` to `n-1`).
- For each day `i`, check if the price is higher than the previous day's price (`prices[i] > prices[i-1]`)
- If it is, add the difference `prices[i] - prices[i-1]` to `maxProfit`.
- After the loop finishes, `maxProfit` will hold the maximum possible profit.

# Solutions
### CSharp

```csharp
public class Solution { public int MaxProfit ( int [] prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . Length ; ++ i ) { ans += Math . Max ( 0 , prices [ i ] - prices [ i - 1 ]); } return ans ; } }
```

### Java

```java
class Solution { public int maxProfit ( int [] prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . length ; ++ i ) { ans += Math . max ( 0 , prices [ i ] - prices [ i - 1 ]); } return ans ; } }
```

### JavaScript

```javascript
/** * @param {number[]} prices * @return {number} */ var maxProfit = function (
  prices,
) {
  let ans = 0;
  for (let i = 1; i < prices.length; i++) {
    ans += Math.max(0, prices[i] - prices[i - 1]);
  }
  return ans;
};

```

### CPP

```cpp
class Solution { public: int maxProfit ( vector < int >& prices ) { int ans = 0 ; for ( int i = 1 ; i < prices . size (); ++ i ) ans += max ( 0 , prices [ i ] - prices [ i - 1 ]); return ans ; } };
```

### Python

```python
''' >>> from itertools import pairwise >>> dirs = (-1, 0, 1, 0, -1) >>> pairwise(dirs) <itertools.pairwise object at 0x104dbe470> >>> list(pairwise(dirs)) [(-1, 0), (0, 1), (1, 0), (0, -1)] ''' class Solution : def maxProfit ( self , prices : List [ int ]) -> int : return sum ( max ( 0 , b - a ) for a , b in pairwise ( prices )) class Solution : def maxProfit ( self , prices : List [ int ]) -> int : return sum ( max ( 0 , prices [ i ] - prices [ i - 1 ]) for i in range ( 1 , len ( prices )) ) class Solution : def maxProfit ( self , prices : List [ int ]) -> int : return sum ( prices [ i ] - prices [ i - 1 ] for i in range ( 1 , len ( prices )) if prices [ i ] > prices [ i - 1 ] ) ############ class Solution ( object ): def maxProfit ( self , prices ): """ :type prices: List[int] :rtype: int """ ans = 0 for i in range ( 1 , len ( prices )): if prices [ i ] > prices [ i - 1 ]: ans += prices [ i ] - prices [ i - 1 ] return ans
```