package com.fishercoder.solutions;

/**
 * 714. Best Time to Buy and Sell Stock with Transaction Fee
 *
 * 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 = 2
 Output: 8
 Explanation: The maximum profit can be achieved by:
 Buying at prices[0] = 1
 Selling at prices[3] = 8
 Buying at prices[4] = 4
 Selling at prices[5] = 9
 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

 Note:
 0 < prices.length <= 50000.
 0 < prices[i] < 50000.
 0 <= fee < 50000.
 */
public class _714 {
    public static class Solution1 {
        /**O(n) time
         * O(n) space
         * credit: https://discuss.leetcode.com/topic/108009/java-c-clean-code-dp-greedy
         * */
        public int maxProfit(int[] prices, int fee) {
            int n = prices.length;
            if (n < 2) {
                return 0;
            }
            int[] hold = new int[n];
            int[] sell = new int[n];
            hold[0] = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                hold[i] = Math.max(hold[i - 1], sell[i - 1] - prices[i]);
                sell[i] = Math.max(sell[i - 1], hold[i - 1] - fee + prices[i]);
            }
            return sell[n - 1];
        }
    }

    public static class Solution2 {
        /**O(n) time
         * O(1) space
         * credit: https://leetcode.com/articles/best-time-to-buy-and-sell-stock-with-transaction-fee/
         *
         * cash: the max profit we could have if we did not have a share of stock in hand
         * hold: the max profit we could have if we hold one share of stack in hand
         *
         * to transition from the i-th day to the i+1 th day, we have two options:
         * 1. sell our stock: cash = Math.max(cash, hold + prices[i] - fee)
         * 2. buy a stock: hold = Math.max(hold, cash - prices[i])
         * */
        public int maxProfit(int[] prices, int fee) {
            int cash = 0;
            int hold = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                cash = Math.max(cash, hold + prices[i] - fee);
                hold = Math.max(hold, cash - prices[i]);
            }
            return cash;
        }
    }
}

@@ -33,897 +33,8 @@
 s;%0A%0A
-/**%0A * 714. Best Time to Buy and Sell Stock with Transaction Fee%0A *%0A * Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i;%0A * and a non-negative integer fee representing a transaction fee.%0A * You may complete as many transactions as you like,%0A * but you need to pay the transaction fee for each transaction.%0A * 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.)%0A%0A Return the maximum profit you can make.%0A%0A Example 1:%0A Input: prices = %5B1, 3, 2, 8, 4, 9%5D, fee = 2%0A Output: 8%0A Explanation: The maximum profit can be achieved by:%0A Buying at prices%5B0%5D = 1%0A Selling at prices%5B3%5D = 8%0A Buying at prices%5B4%5D = 4%0A Selling at prices%5B5%5D = 9%0A The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.%0A%0A Note:%0A 0 %3C prices.length %3C= 50000.%0A 0 %3C prices%5Bi%5D %3C 50000.%0A 0 %3C= fee %3C 50000.%0A */%0A
 publ
@@ -88,32 +88,44 @@
 n1 %7B%0A        /**
+%0A         * 
 O(n) time%0A      
@@ -229,34 +229,32 @@
 -greedy%0A        
- *
  */%0A        publ
@@ -821,16 +821,28 @@
      /**
+%0A         * 
 O(n) tim
@@ -970,32 +970,36 @@
 -fee/%0A         *
+ %3Cp%3E
 %0A         * cash
@@ -1167,16 +1167,20 @@
        *
+ %3Cp%3E
 %0A       
@@ -1398,24 +1398,24 @@
 ces%5Bi%5D)%0A
+
         
  * */%0A  
@@ -1406,18 +1406,16 @@
         
- *
  */%0A    

refactor 714