class Solution {public int maxProfit(int[] prices) {int ans = 0;int minPrice = prices[0];for (int p : prices) {ans = Math.max(ans, p - minPrice);minPrice = Math.min(minPrice, p);}return ans;}
}
public class Solution {public boolean canJump(int[] nums) {int k = 0;//可以达到的最远距离for (int i = 0; i < nums.length; i++) {if (i > k) return false;k = Math.max(k, i + nums[i]);//维护可以达到的最远距离}return true;}
}
class Solution {public int jump(int[] nums) {int ans = 0;int st = 0;int ed = 0;while(ed<nums.length-1){//在index之内int maxP = 0;for(int i = st;i<=ed;i++){//能跳到的最远距离maxP =Math.max(maxP,i + nums[i]);}st = ed;//下次起跳范围的起点ed = maxP;//下次起跳范围的终点ans ++;}return ans;}
}
class Solution {public List<Integer> partitionLabels(String S) {char[] s = S.toCharArray();int n = s.length;int[] last = new int[26];for(int i=0;i<n;i++){last[s[i] - 'a'] = i;//每个字母最后出现的下标}List<Integer> ans = new ArrayList<>();int st = 0,ed = 0;for(int i=0;i<n;i++){ed = Math.max(ed,last[s[i] - 'a']);//更新当前区间右端点最大值if(ed == i){//当前区间合并完毕 已经到达最远的地方了这个字母ans.add(ed-st+1);//区间长度加入答案中st = i+1;//下一个区间的左端点}}return ans;}
}
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];//dp[i]表示i元钱所需要的最小的硬币数量Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int i=0;i<coins.length;i++){//只考虑前i个硬币for(int j=coins[i];j<=amount;j++){//顺序完全背包if(dp[j-coins[i]] != Integer.MAX_VALUE){dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return dp[amount] != Integer.MAX_VALUE?dp[amount]:-1;}
} 
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int max_Len = 0;//最长的长度for (String word : wordDict) {max_Len = Math.max(max_Len, word.length());//记录最长的长度}Set<String> words = new HashSet<>(wordDict);//去重int n = s.length();//以这个地方-1为结尾 看看子串受否在word中如果在那么就找到了子问题int[] memo = new int[n + 1];Arrays.fill(memo, -1); // -1 表示没有计算过return dfs(n, max_Len, s, words, memo) == 1;}private int dfs(int i, int max_Len, String s, Set<String> words, int[] memo) {if (i == 0) { // 成功拆分！return 1;}if (memo[i] != -1) { // 之前计算过return memo[i];}for (int j = i - 1; j >= Math.max(i - max_Len, 0); j--) {if (words.contains(s.substring(j, i)) && dfs(j, max_Len, s, words, memo) == 1) {return memo[i] = 1; // 记忆化}}return memo[i] = 0; // 记忆化}
}
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int maxLen = 0;for (String word : wordDict) {maxLen = Math.max(maxLen, word.length());}Set<String> words = new HashSet<>(wordDict);int n = s.length();boolean[] f = new boolean[n + 1];f[0] = true;for (int i = 1; i <= n; i++) {for (int j = i - 1; j >= Math.max(i - maxLen, 0); j--) {if (f[j] && words.contains(s.substring(j, i))) {f[i] = true;break;}}}return f[n];}
} 
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int maxLen = 0;for (String word : wordDict) {maxLen = Math.max(maxLen, word.length());}Set<String> words = new HashSet<>(wordDict);int n = s.length();boolean[] f = new boolean[n + 1];f[0] = true;for (int i = 1; i <= n; i++) {//以i-1为结尾for (int j = i - 1; j >= Math.max(i - maxLen, 0); j--) {if (f[j] && words.contains(s.substring(j, i))) {//注意这两个条件f[i] = true;//存在从头开始并以i为结尾的子串break;}}}return f[n];}
}
class Solution {public int lengthOfLIS(int[] nums) {if(nums.length==0)return 0;int[] dp = new int[nums.length];int res = 0;Arrays.fill(dp,1);for(int i=0;i<nums.length;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i])dp[i] = Math.max(dp[i],dp[j]+1);}res = Math.max(res,dp[i]);}return res;}
}
import java.util.TreeSet;class Solution {public int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}TreeSet<Integer> d = new TreeSet<>();for (int num : nums) {// 找到大于等于num的最小元素Integer ceil = d.ceiling(num);if (ceil == null) {// 如果没有大于等于num的元素，则直接添加numd.add(num);} else {// 如果存在大于等于num的元素，则替换为numd.remove(ceil);d.add(num);}}// 返回集合的大小，即最长递增子序列的长度return d.size();}
}
class Solution {public int lengthOfLIS(int[] nums) {int len = 1, n = nums.length;if (n == 0)return 0;int[] d = new int[n + 1];d[len] = nums[0];for (int i = 1; i < n; ++i) {if (nums[i] > d[len]) {d[++len] = nums[i];//如果满足递增的话就直接加入} else {//不满足的话就找找它应该替代那个位置 替代掉int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0while (l <= r) {int mid = (l + r) >> 1;if (d[mid] < nums[i]) {pos = mid;l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nums[i];//替代这个位置}}return len;}
}
class Solution {public int maxProduct(int[] nums) {int n = nums.length;int []f_Max = new int[n];int []f_Min = new int[n];f_Max[0] = f_Min[0] = nums[0];for(int i=1;i<n;i++){int x = nums[i];//将x加到右端点为i-1的(乘积最大/最大)子串后面//或者单独组成一个子串 只有x一个元素f_Max[i] = Math.max(Math.max(f_Max[i-1]*x,f_Min[i-1]*x),x);f_Min[i] = Math.min(Math.min(f_Max[i-1]*x,f_Min[i-1]*x),x);}return Arrays.stream(f_Max).max().getAsInt();}
}class Solution {public int maxProduct(int[] nums) {int ans = Integer.MIN_VALUE; // 注意答案可能是负数int fMax = 1;int fMin = 1;for (int x : nums) {int mx = fMax;fMax = Math.max(Math.max(fMax * x, fMin * x), x);fMin = Math.min(Math.min(mx * x, fMin * x), x);ans = Math.max(ans, fMax);}return ans;}
} 
class Solution {public boolean canPartition(int[] nums) {int s = 0;for (int x : nums)s += x;if (s % 2 != 0)return false;//不是偶数不行s /= 2; // 注意这里把 s 减半了boolean[] f = new boolean[s + 1];f[0] = true;int s2 = 0;for (int x : nums) {//01背包s2 = Math.min(s2 + x, s);//分割数组之后较小的那个数组计算for (int j = s2; j >= x; j--) {f[j] = f[j] || f[j - x];//有1则1}if (f[s]) {return true;}}return false;}
}
