LeetCode 75
Best Time to Buy and Sell Stock III
- Problem
- LC 123
- Topic
- DP Multidim
- File
- official75_LC123BestTimeToBuyAndSellStockIII.java
- Path
- pkg5leetcode/official75/official75_LC123BestTimeToBuyAndSellStockIII.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC123BestTimeToBuyAndSellStockIII.java
- Approach
- DP track profit after 0/1/2 transactions.
- 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 III | LC 1235 * APPROACH: DP track profit after 0/1/2 transactions.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class official75_LC123BestTimeToBuyAndSellStockIII {9 static int maxProfit(int[] prices) {10 int buy1 = Integer.MIN_VALUE / 2, sell1 = 0;11 int buy2 = Integer.MIN_VALUE / 2, sell2 = 0;12 for (int p : prices) {13 buy1 = Math.max(buy1, -p);14 sell1 = Math.max(sell1, buy1 + p);15 buy2 = Math.max(buy2, sell1 - p);16 sell2 = Math.max(sell2, buy2 + p);17 }18 return sell2;19 }20 21 public static void main(String[] args) {22 check(maxProfit(new int[]{3,3,5,0,0,3,1,4}) == 6, "case1");23 check(maxProfit(new int[]{1,2,3,4,5}) == 4, "case2");24 System.out.println("all tests passed");25 }26 27 static void check(boolean cond, String name) {28 if (!cond) throw new AssertionError("FAILED: " + name);29 System.out.println(" PASS " + name);30 }31}