309. Best Time to Buy and Sell Stock with Cooldown
class Solution { public int maxProfit(int[] prices) { if(prices == null || prices.length <= 1) return 0; int n = prices.length; int[] hold = new int[n]; int[] unhold = new int[n]; hold[0] = -prices[0]; for(int i = 1; i < n; i++){ if(i == 1){ hold[i] = Math.max(hold[i - 1], -prices[1]); }else{ hold[i] = Math.max(hold[i - 1], unhold[i - 2] - prices[i]); } unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]); } return unhold[n - 1]; } }
334. Increasing Triplet Subsequence
如果m1大于等于当前数字,则将当前数字赋给m1;如果m1小于当前数字且m2大于等于当前数字,那么将当前数字赋给m2,一旦m2被更新了,说明一定会有一个数小于m2,那么我们就成功的组成了一个长度为2的递增子序列,所以我们一旦遍历到比m2还大的数,我们直接返回ture。如果我们遇到比m1小的数,还是要更新m1,有可能的话也要更新m2为更小的值,毕竟m2的值越小,能组成长度为3的递增序列的可能性越大
class Solution { public boolean increasingTriplet(int[] nums) { int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE; for(int a : nums){ if(m1 >= a) m1 = a; else if(m2 >= a) m2 = a; else return true; } return false; } }