This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Your are given an array of integers `prices`

, for which the `i`

-th element is the price of a given stock on day `i`

; and a non-negative integer `fee`

representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

**Example 1:**

Input:prices = [1, 3, 2, 8, 4, 9], fee = 2Output:8Explanation:The maximum profit can be achieved by:

**Note:**

`0 < prices.length <= 50000`

.`0 < prices[i] < 50000`

.`0 <= fee < 50000`

.b'

\n\n#### Approach #1: Dynamic Programming [Accepted]

\n\n\n

\n

'
**Intuition and Algorithm**

At the end of the `i`

-th day, we maintain `cash`

, the maximum profit we could have if we did not have a share of stock, and `hold`

, the maximum profit we could have if we owned a share of stock.

To transition from the `i`

-th day to the `i+1`

-th day, we either sell our stock `cash = max(cash, hold + prices[i] - fee)`

or buy a stock `hold = max(hold, cash - prices[i])`

. At the end, we want to return `cash`

. We can transform `cash`

first without using temporary variables because selling and buying on the same day can\'t be better than just continuing to hold the stock.

**Python**

class Solution(object):\n def maxProfit(self, prices, fee):\n cash, hold = 0, -prices[0]\n for i in range(1, len(prices)):\n cash = max(cash, hold + prices[i] - fee)\n hold = max(hold, cash - prices[i])\n return cash\n

**Java**

class Solution {\n public int maxProfit(int[] prices, int fee) {\n int cash = 0, hold = -prices[0];\n for (int i = 1; i < prices.length; i++) {\n cash = Math.max(cash, hold + prices[i] - fee);\n hold = Math.max(hold, cash - prices[i]);\n }\n return cash;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the number of prices.

\n \n - \n
Space Complexity: , the space used by

\n`cash`

and`hold`

. \n

\n

Analysis written by: @awice.

\n