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的元素，则直接添加num
                d.add(num);
            } else {
                // 如果存在大于等于num的元素，则替换为num
                d.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 设为 0
                while (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;
    }
}