LeetCode 75
Best Time to Buy and Sell Stock with Transaction Fee
- Problem
- LC 714
- Topic
- DP 1D
- File
- official75_LC714BestTimeToBuyAndSellStockWithTransactionFee.java
- Path
- pkg5leetcode/official75/official75_LC714BestTimeToBuyAndSellStockWithTransactionFee.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC714BestTimeToBuyAndSellStockWithTransactionFee.java
- Approach
- DP cash vs holding stock each day.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Best Time to Buy and Sell Stock with Transaction Fee | LC 7145 * APPROACH: DP cash vs holding stock each day.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class official75_LC714BestTimeToBuyAndSellStockWithTransactionFee {9 static int maxProfit(int[] prices, int fee) {10 int cash = 0, hold = Integer.MIN_VALUE / 2;11 for (int p : prices) {12 int prev = cash;13 cash = Math.max(cash, hold + p - fee);14 hold = Math.max(hold, prev - p);15 }16 return cash;17 }18 19 public static void main(String[] args) {20 check(maxProfit(new int[]{1,3,2,8,4,9}, 2) == 8, "case1");21 check(maxProfit(new int[]{2,1,4,5,2,9,7}, 3) == 5, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}