package leetcode.editor.cn;

public class MySolution {
    public static void main(String[] args) {
        Solution solution = new MySolution().new Solution();
        // TO TEST...
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void method(int x) {

        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        // 动态规划
        int[] dp = new int[n];
        if (n == 1) {
            return nums[0];
        }

        // 边界
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i=2; i<n; i++) {
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }

        return dp[n-1];
    }
}

// 从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。
// 考虑使用动态规划
// dp[i][j]表示从i到j字符串是否是回文，然后向外扩散，当然边界是长度为1和为2的子串
class Solution {
    public String longestPalindrome(String s) {
        // 回文子串问题，动态规划
        char[] chars = s.toCharArray();
        int n = chars.length;
        boolean[][] dp = new boolean[n][n];
        if (n < 2) {
            return s;
        }

        int ansCount = 0;
        String ansStr = "" + chars[0]; // 初始化，一个字符

        // 边界
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 注意，这个动态规划需要从子串小的到大的，step=2，表示子串长度为2的情况；step=n，表示长度为n的情况
        // 所以考虑下面的i的末尾的时候，只要考虑step=n的时候，i=0需要成立
        for (int step = 2; step <= n; step++) {
            for (int i = 0; i < n-step+1; i++) {
                int j = i + step - 1; // 注意从两个开始
                if (chars[i] == chars[j]) {
                    // 若只有两个
                    if (step == 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                } else {
                    dp[i][j] = false;
                }

                // 因为题目要找最大的，所以看是否是最大的
                if (dp[i][j] && step > ansCount) {
                    ansCount = step;
                    ansStr = s.substring(i, j+1);
                }
            }
        }

        return ansStr;
    }
}

class Solution {
    /**
    这道题目求所有的分割方案，所以考虑使用回溯+dfs的方法
    在0～i-1已经有的了的情况下，后面的i~n-1使用i, i~i+1, i~i+2, ..., i~n-1这样的方法加入
    当然加入的需要本身就是回文串，所以首先使用动态规划来预处理，回文串
    dp预处理回文串  +    dfs回溯找方案
     */
    public List<List<String>> partition(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        
        // ij表示从s的i到j的子串
        boolean[][] dp = new boolean[n][n];

        // 边界包含在下面的判断条件中了
        for (int step = 1; step <= n; step++) {
            for (int i = 0; i < n - step + 1; i++) {
                int j = i + step - 1;

                if (step == 1) {
                    dp[i][j] = true;
                } else if (step == 2) {
                    if (chars[i] == chars[j]) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = false;
                    }
                } else {
                    if (chars[i] == chars[j]) {
                        dp[i][j] = dp[i+1][j-1];
                    } else {
                        dp[i][j] = false;
                    }
                }
            }
        }

        List<List<String>> anses = new ArrayList();
        // dfsTrace(anses, new ArrayList<>(), 0, s, dp);
        dfsTrace(anses, new ArrayList<>(), 0, chars, dp);
        return anses;
    }

    // 使用回溯，得到所有可能的方案
    public void dfsTrace(List<List<String>> anses, List<String> curAns, int curIndex, char[] chars, boolean[][] dp) {
        if (curIndex == chars.length) {
            
            anses.add(new ArrayList<>(curAns));
            return;
        }

        // 当前这个i是没有被用过的，因为main中调用的时候从0开始（0也没用），而且判断结束是判断到length
        // 注意，只有一个的也要
        for (int i = curIndex; i < chars.length; i++) {
            if (dp[curIndex][i]) {
                curAns.add(new String(Arrays.copyOfRange(chars, curIndex, i + 1)));
                dfsTrace(anses, curAns, i + 1, chars, dp);
                curAns.remove(curAns.size() - 1);
            }
        }
    }

    // // 使用回溯，得到所有可能的方案
    // public void dfsTrace(List<List<String>> anses, List<String> curAns, int curIndex, String s, boolean[][] dp) {
    //     if (curIndex == s.length()) {
            
    //         anses.add(new ArrayList<>(curAns));
    //         return;
    //     }

    //     // 当前这个i是没有被用过的，因为main中调用的时候从0开始（0也没用），而且判断结束是判断到length
    //     // 注意，只有一个的也要
    //     for (int i = curIndex; i < s.length(); i++) {
    //         if (dp[curIndex][i]) {
    //             curAns.add(s.substring(curIndex, i + 1));
    //             dfsTrace(anses, curAns, i + 1, s, dp);
    //             curAns.remove(curAns.size() - 1);
    //         }
    //     }
    // }
}

class Solution {
    /**
    动态规划，dp[i]表示从0～i的最大子数组和
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        // dp表示已自己结尾的数组最大值，所以一定要包括自己的
        int[] dp = new int[n];
        int ans = 0;

        // 边界
        dp[0] = nums[0];
        
        for (int i = 1; i < n; i++) {
            // 指取自己，还是自己和前一段，两者的较大值
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }

        return ans;
    }
}

// 注意，记忆这一个，简单一点
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length-1;

        // 返回第一个>=target的
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            // 本来若nums中全部不同，那么只会有一个相等，那么单独判断下，如果有很多相等，而且要放到相等的后面，那么还是left = mid + 1;
            // 一样的，如果要放大相等的最前面，那么等号放到right = right-1中去
            if (nums[mid] == target) {
                left = mid; // 因为最终left是结果，所以直接这样了，当然此处return mid也是可以的
                break;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
			
      	// 因为while中使用的是<=，所以在不是等于的情况下，最终形态left = right + 1
      	// 即，nums[right] < target < nums[left]，所以要插入的位置就是在left处
      	// 因为left初始化是0，所以插入0的位置也是可以的（right=-1）；插入nums.length也是可以的，right没动过的情况下。
        return left;
    }
}

// 方法一：动态
// 这道题目数据量只有2500，所以可以不用贪心
class Solution {
    // 动态规划
    // dp[i]代表0～i中最长递增子序列长度
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int ans = 1;

        // 边界
        Arrays.fill(dp, 1);

        for (int i=1; i<nums.length; i++) {
            for (int j=0; j<i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }

        // 最后的答案是dp[i]中最大的一个
        return ans;
    }
}

// 当LCS问题，其中一个序列的元素各不相同时，转化为LIS问题，那么就可以用这里面的方法一或者方法二，对这个各不相同的序列的下标映射到另一个的数组 使用。
// 方法二：动态+贪心+二分
// 若数据量比如有10e5，那么只用动态O(n^2)会超时，所以需要加入贪心+二分
// 另外再使用一个数组g，g[i]表示长度为i的最长升序子序列的末尾元素的最小值
// 可以知道g[i]其实是单调递增的
// 然后再更新dp[i]的时候，如果nums[i]>g[len]，直接加到g数组的末尾；
// 否则，只要找到g中g[k-1] < nums[i] < g[k]，第一个比num[i]小的g[k-1]，并更新g[k] = nums[i]，（因为加入后，k-1是要+1的）
package leetcode.editor.cn;

import java.util.*;

public class P300LongestIncreasingSubsequence {
    public static void main(String[] args) {
        Solution solution = new P300LongestIncreasingSubsequence().new Solution();
        // TO TEST...
        System.out.println(solution.lengthOfLIS(new int[]{7,7,7,7,7,7,7}));
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 动态规划
        // dp[i]代表0～i中最长递增子序列长度
        public int lengthOfLIS(int[] nums) {
            int[] g = new int[nums.length + 1];
            int len = 1;

            // 边界
            g[len] = nums[0];   // g[1]需要放入

            // 递推
            for (int i=1; i<nums.length; i++) {
                int left = 1, right = len; // g是从1～nums.length的，所以这么写，如果0～len-1就写0-len-1
                // 需要找到第一个比nums[i]小的，然后加到这一串子序列上去，这串子序列的长度+1
                while (left <= right) {
                    int mid = left + ((right - left) >> 1);
                    if (g[mid] == nums[i]) {
                        left = mid; // 若相同的不能加入，就是mid，否则等号且是放到最右边的话还是left=mid+1
                        break;
                    } else if (g[mid] > nums[i]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }

                // 因为while是有=号的，所以最终形成的是g[right] < nums[i] < g[left]
              	// 此处本来是right的，但是left正好等于 right + 1
                len = Math.max(left, len);
                g[left] = nums[i];
            }

            // 最后的答案是g的长度
            return len;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (e1, e2) -> {
            if (e1[0] == e2[0]) {
              	// 注意，此处按照w相同之后，降序排列，这样就能阻止w相同之后，h递增就能嵌套的问题（题目要求都大于才能嵌套）
                return e2[1] - e1[1];
            }

            return e1[0] - e2[0];
        });

        int n = envelopes.length;
        // int[] dp = new int[n];
        int[] g = new int[n+1];
        int ans = 1;

        // 边界
        // Arrays.fill(dp, 1);
        g[1] = envelopes[0][1];

        for (int i = 1; i < n; i++) {
            int left = 1, right = ans;

            // 找到第一个>的，等于的还是没用
            while (left <= right) {
                int mid = left + (right - left >> 1);
                if (envelopes[i][1] == g[mid]) {
                    left = mid; // 因为相等的时候，长度只能这么点
                    break;
                } else if (envelopes[i][1] < g[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // 这个找到就是长度
            ans = Math.max(ans, left);
          	// 这里不需要用Math.min的原因是left的元素一定>=g[left]的，而且如果left在最后面（比所有元素都大），那么用Math.min反而不对（需要给g全部初始化，然后这个left在最后时单独判断）
            g[left] = envelopes[i][1];
        }

        return ans;
    }
}

/**
* 通过找在s中到最长的不下降子序列，长度为len，然后总len-此len即可
* 注意此处是序列，不需要连续，只要顺序相同
* 由于长度为10e5，所以单纯动态不够，需要加上贪心二分
* g[i]代表最长子序列长度为i的时候，末尾元素的最小值
* 可以得知g[i]是单调递增的
*/
class Solution {
  public int minFlipsMonoIncr(String s) {
    int n = s.length();
    int[] g = new int[n + 1]; // 因为长度可以从1～n
    int gLen = 1;

    // 边界，最开始长度为1的时候，是第一个字符
    g[gLen] = s.charAt(0) - '0';

    for (int i = 1; i < s.length(); i++) {
      int left = 1, right = gLen; // g的有效数组是，1～size，最两个极端要么加到1，要么加到length+1
      int num = s.charAt(i) - '0';
      while (left <= right) {
        int mid = left + ((right - left) >> 1);
        // 本来若nums中全部不同，那么只会有一个相等，那么单独判断下，如果有很多相等，而且要放到相等的后面，那么还是left = mid + 1;
        // 一样的，如果要放大相等的最前面，那么等号放到right = right-1中去
        if (g[mid] <= num) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }

      g[left] = num; // 找到了g[left-1] < num < g[left]的，num加入left-1 + 1的g中
      gLen = Math.max(gLen, left);
    }

    return n - gLen;
  }
}



// 或者动态规划
/**
* 通过动态规划
* dp[i][0]代表i这一位到0需要的次数，那么前面的需要全为0
* dp[i][1]代表i这一位要变到1需要的次数，那么可以是dp[i][0] 和dp[i][1]的比较
* 由于dp[i]只和dp[i-1]有关，所以也可以不用数组，只要维护前面状态的两个数值即可
*/
class Solution {
  public int minFlipsMonoIncr(String s) {
    int len = s.length();
    int[][] dp = new int[len][2];

    // 边界
    dp[0][0] = s.charAt(0) == '0' ? 0 : 1;
    dp[0][1] = s.charAt(0) == '0' ? 1 : 0;

    for (int i = 1; i < len; i++) {
      dp[i][0] = dp[i-1][0] + s.charAt(0) == '0' ? 0 : 1;
      dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]) + s.charAt(0) == '0' ? 1 : 0;
    }

    return Math.max(dp[len-1][0], dp[len-1][1]);
  }
}

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // dp表示已自己结尾的最长子序列长度
        int[] dp = new int[n];
        int[] g = new int[n]; // 用g来标志以i结尾的，最长子序列的个数有多少个

        // 边界
        int maxCount = 1;
        Arrays.fill(dp, 1); // 每个自己都能组成一个
        Arrays.fill(g, 1); // 每个自己都能组成一个

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        g[i] = g[j]; // 目前以i结尾的最长序列的个数就是g[j]个
                    } else if (dp[i] == dp[j] + 1) {
                        // 又有一样最长的子序列了，那么加上
                        g[i] += g[j];
                    }
                }
            }
            
            maxCount = Math.max(maxCount, dp[i]);
        }

        int finalMaxCount = maxCount;
        return IntStream.range(0, dp.length).filter(index -> dp[index] == finalMaxCount).map(index -> g[index]).sum();
    }
}

import java.util.*;
import java.util.stream.IntStream;

/**
 * 求最长上升子序列，以及该最长上生子序列的第一位
 */
// 未验证
public class Main1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

        int[] dp = new int[n];

        // 边界
        // 用来存储以第i个数结尾的最长子序列的第一个
        // 初始化，应该是g[i] = i吧
        int[] g = IntStream.range(0, n).map(i -> nums[i]).toArray();
        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        g[i] = g[j];
                    }
                    // 相等不做了吧，第一个就行了吧
                }
            }
        }

        int ansIndex = 0;
        int maxCount = 0;
        for (int i = 0; i < n; i++) {
            if (maxCount < dp[i]) {
                maxCount = dp[i];
                ansIndex = i;
            }
        }
        System.out.println(g[ansIndex] + " " + maxCount);
    }
}

/**
* 使用dp
* dp[i][j]代表text1[0~i-1]，text2[0~j-1]的公共最长子序列，注意此处的关系
* 注意此处题目中的子序列不用连续，顺序一样就好
*/
class Solution {
  public int longestCommonSubsequence(String text1, String text2) {
    int len1 = text1.length(), len2 = text2.length();
    int[][] dp = new int[len1+1][len2+1];

    // 边界
    for (int i = 0; i < len1; i++) {
      dp[i][0] = 0;
    }
    for (int i = 0; i < len2; i++) {
      dp[0][i] = 0;
    }

    // 此处因为dp有0的边界，所以都从1开始，而text都应该从0开始的，所以后面-1
    for (int i = 1; i <= len1; i++) {
      char c1 = text1.charAt(i-1);
      for (int j = 1; j <= len2; j++) {
        char c2 = text2.charAt(j-1);
        if (c1 == c2) {
          dp[i][j] = dp[i-1][j-1] + 1;
        } else {
          dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
      }
    }

    return dp[len1][len2];
  }
}

class Solution {
    // 枚举 + LCS， 可以减枝
    public int findLUSlength(String[] strs) {
        int n = strs.length;
        int ans = 0;

        // i是子序列，然后遍历下，看看是不是其中一个的子序列，当然需要去除自己
        for (int i = 0; i < n; i++) {
            // 枚举，当前的i是不是下面每一个的子集，如果都不是，那么与ans比较
            // 减枝，如果strs[i].length() <= ans，就算是也没必要了
            if (strs[i].length() > ans) {
                boolean flag = false;
                for (int j = 0; j < n; j++) {
                    if (j != i && checkLCS(strs[j], strs[i])) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) { ans = strs[i].length(); }
            }
            
        }

        return ans == 0 ? -1: ans;
    }

    public boolean checkLCS(String s, String childS) {
        int n1 = s.length(), n2 = childS.length();

        int[][] dp = new int[n1+1][n2+1];

        // 边界，dp[i][0], dp[0][i] = 0

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (s.charAt(i-1) == childS.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        if (dp[n1][n2] == n2) { return true; }
        return false;
    }
}

/**
* 可以求出公共子序列，然后target的len减去 公共子序列的len即可
* 当两个数组求公共子序列时（LCS），当有一个数组元素各不相同时，可以转为（LIS）
* 具体做法是，先map存储target中的元素和下标，然后一个个遍历arr（此处需要存的是元素不重复的下标）
* 若和target有公共元素（与map中是有contains该key），list中存储该公共元素的target中的下标
* 注意，list中的元素顺序是按照arr来的，而存储的是target的下标
*/
class Solution {
    public int minOperations(int[] target, int[] arr) {
        // 先将LCS转换为LIS的前序工作做好
        Map<Integer, Integer> map = IntStream.range(0, target.length).boxed()
                .collect(Collectors.toMap(index -> target[index], Function.identity(), (a, b) -> a));
        int[] indexNums = Arrays.stream(arr).filter(map::containsKey).map(map::get).toArray();

        int n = indexNums.length;
        if (n == 0) {
            return target.length;
        }

        int[] dp = new int[n];
        // g[len] = x，表示该长度下的最长递增子序列以某个数结尾，这个数最小是x，可以知道x是递增的
        // 那么我每次遍历i的时候，只要找到这个x，然后dp[i] + 1即可
        // 就不需要像朴素LIS一样重新遍历一遍查找
        int[] g = new int[n + 1];

        // 边界
        Arrays.fill(g, Integer.MAX_VALUE);
        g[0] = -1; // 注意，因为0不参加在里面，但是需要递增

        for (int i = 0; i < n; i++) {
            // 使用二分找到第一个小于nums[i]的g，严格递增不能等于
            int left = 0, right = i;
            while (left <= right) {
                int mid = left + (right - left >> 1);
                if (g[mid] >= indexNums[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // 注意，此处的right代表的是长度，而不是下标，right=-1表示未找到
            dp[i] = right == -1 ? 1 : right + 1;
            // 注意这里的比较不要搞错
            g[dp[i]] = Math.min(indexNums[i], g[dp[i]]);
        }

        return target.length - Arrays.stream(dp).max().getAsInt();
    }
}

class Solution {
    public int numDecodings(String s) {
        // 加个空格哨兵，可以减少前导零
        s = ' ' + s;
        int n = s.length();
        int[] dp = new int[s.length()];

        // 边界
        dp[0] = 1;

        for (int i=1; i<n; i++) {
            int a = s.charAt(i) - '0';
            int b = (s.charAt(i-1) - '0') * 10 + a; // 在i=1的时候，肯定不满足，所以不会运行到下一个if，所以没关系

            if (a >= 1 && a <= 9) {
                dp[i] = dp[i-1];
            }
            if (b >= 10 && b <= 26) {
                dp[i] += dp[i-2];
            }

        }

        return dp[n-1];
    }
}

class Solution {
    /**
    动态规划
    由于有选和不选两种状态，所以需要二维动态规划
    还有第一间的问题，第一间选和不选，使用两次动态规划完成
     */
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) { return 0; }
        if (n == 1) { return nums[0]; }

        int[][] dp = new int[n][n];

        // 第一间不选，dp[0][0]和dp[0][1]都是0
        for (int i=1; i<=n-2; i++) { // 最后一间，需要根据第一件单独判断
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        // 因为第一间不选，所以最后一间根据最后第二件来就好
        // 此处最后一件不选，dp[n-1][0]不用考虑，因为选了之后的考虑了
        int a = Math.max(dp[n-2][0]+nums[n-1], dp[n-2][1]);

        // 第一件可以选，然后最后的判断只要判断选的就好了，因为不选的已经在上面了
        dp[0][0] = 0; dp[0][1] = nums[0];
        for (int i=1; i<=n-2; i++) { // 最后一间，需要根据第一件单独判断
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        // 第一件选，最后一件肯定不选
        int b = Math.max(dp[n-2][0], dp[n-2][1]);

        return Math.max(a, b);
    }
}

class Solution {
    // 使用动态规划
    // dp[i][j]表示i到j之间能选择的确保的最小金额
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+2][n+2]; // 这里+1还不够，因为下面r最大为nn，然后i+1为n+1，其实要到[n+1]了

        // 边界，全为0即可

        // 然后dp，可以看出需要从小的，到大的，所以从lenlen=2开始
        for (int step=2; step<=n; step++) {
            for (int l=1; l<=n-step+1; l++) {
                int r = l + step - 1;
                
                dp[l][r] = Integer.MAX_VALUE;
                for (int i=l; i<=r; i++) { // 遍历l～r中的所有
                    int cur = Math.max(dp[l][i-1], dp[i+1][r]) + i;
                    dp[l][r] = Math.min(cur, dp[l][r]);
                }
            }
        }

        return dp[1][n];
    }
}

/**
3 5
2 4 1
10 5 4

14
9
*/

/**
个人感觉，恰好和少于等于，最主要的区别在于边界。
少于等于的话，直接边界是0就可以。
但是如果是正好的话，边界需要设置0x3f3f3f3f或者-0x3f3f3f3f
 */
import java.util.Arrays;
import java.util.Scanner;

public class App {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int total = scanner.nextInt();
        scanner.nextLine();

        int[] w = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        int[] v = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();

        // 二维数组
        // 少于等于
        int[][] dp1 = new int[n+1][total+1];
        // 少于等于边界
        for (int i = 0; i < dp1.length; i++) {
            Arrays.fill(dp1[i], 0);
        }

        // 正好
        int[][] dp2 = new int[n+1][total+1];
        // 正好边界
        for (int i = 0; i < dp2.length; i++) {
            Arrays.fill(dp2[i], -0x3f3f3f3f);
        }
        dp2[0][0] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < total + 1; j++) {
                dp1[i][j] = Math.max(dp1[i-1][j], j >= w[i-1] ? dp1[i-1][j-w[i-1]] + v[i-1] : 0);
                // 注意，这里我没有判断是否dp2[i-1][j-w[i-1]]正好有数据，其实如果是个最大复数的话，应该不能恰好装入
                // 但是我最后根据是否小于0判断能否成功了，所以此处让他直接加入了
                dp2[i][j] = Math.max(dp2[i-1][j], j >= w[i-1] ? dp2[i-1][j-w[i-1]] + v[i-1] : -0x3f3f3f3f);
            }
        }

        System.out.println("二维数组 少于等于：" + dp1[n][total]);
        System.out.println("二维数组 正好：" + (dp2[n][total] < 0 ? 0 : dp2[n][total]));

        
        // 一维数组的优化
        // 少于等于
        int[] dp3 = new int[total+1];
        // 少于等于边界
        dp3[0] = 0;

        // 正好
        int[] dp4 = new int[total+1];
        // 正好边界情况
        Arrays.fill(dp4, -0x3f3f3f3f);
        dp4[0] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = total; j >= w[i-1]; j--) {
                dp3[j] = Math.max(dp3[j], dp3[j-w[i-1]] + v[i-1]);
                dp4[j] = Math.max(dp4[j], dp4[j-w[i-1]] + v[i-1]);
            }
        }

        System.out.println("一维数组 少于等于：" + dp3[total]);
        System.out.println("一维数组 少于等于：" + (dp4[total] < 0 ? 0 : dp4[total]));
    }
}

dp[j] = Math.max(dp[j], dp[j-w[i-1]] + v[j-1])

dp[j] = Math.max(dp[j], dp[j-w[i-1]] + v[j-1])

class Solution {
    /**
    使用完全背包，
    先预处理完全平方数，然后第二维的j，代表正好能凑成
    第一维i代表物品编号
    第二维j代表容量
    对于第i位选还是不选，对容量j有影响
     */
    public int numSquares(int n) {
        int sqrtn = (int)(Math.sqrt(n));
        int[][] dp = new int[sqrtn+1][n+1];
      
        // 边界
        // 代表当没有任何硬币的时候，存在凑成总和为 0 的方案，方案所使用的硬币为 0；凑成其他总和的方案不存在。
        for (int i=0; i<=sqrtn; i++) {
            Arrays.fill(dp[i], 0x3f3f3f3f); // 大于109，算作最大值
        }
        dp[0][0] = 0;

        for (int i=1; i<=sqrtn; i++) { // 物品编号，只能是完全平方
            for (int j=0; j<=n; j++) { // 容量
                // 看在j容量下，i编号的物品可以选择多少个
                // k=0，代表没选
                for (int k=0; k*i*i<=j; k++) { 
                    if (dp[i-1][j-k*i*i] != 0x3f3f3f3f) {
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j-k*i*i]+k); // 一定要能够凑成，注意+k
                    }
                }
            }
        }

        return dp[sqrtn][n];
    }		
}

// 也看看一维的
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];

        Arrays.fill(dp, 0x3f3f3f3f);
        dp[0] = 0;
				// 注意这个i*i小于等于n
        for (int i = 1; i * i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j-i*i]+1, dp[j]);
            }
        }

        return dp[n];
    }
}

class Solution {
    /**
    一看就是完全背包问题
    二维，第一维=是金币编号，第二维是剩余金额
    注意，总金额也需要刚好凑成
     */
    public int coinChange(int[] coins, int amount) {
        int INF = Integer.MAX_VALUE;
      	// 注意：如果此处用比最大值小的0x3f3f3f3f，那么就不需要考虑最大值+结果为负数的情况
      	// 那么下面的那个判断就可以不需要了
        int coinZhonglei = coins.length;
        int[][] dp = new int[coinZhonglei+1][amount + 1]; // 0代表金币0，所以zhonglei要+1

        // 边界
        // 代表当没有任何硬币的时候，存在凑成总和为 0 的方案，方案所使用的硬币为 0；凑成其他总和的方案不存在。
        for (int i=0; i<=coinZhonglei; i++) {
            Arrays.fill(dp[i], INF);
        }
        // Arrays.fill(dp[0], INF); // 注意，如果这里只是这样写，那么下面不选择硬币的情况要单独列出来
        dp[0][0] = 0;

        for (int i=1; i<=coinZhonglei; i++) { // 硬币种类
            int coin = coins[i-1];
            
            for (int j=0; j<=amount; j++) {
                // 由于无限制选择，所以需要用k枚举每次选择的个数
                for (int k=0; k*coin<=j; k++) { // 注意这里有等号
                    if (dp[i-1][j-k*coin] != INF) { // 剩下的金额一定要能够用凑成
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][j-k*coin] + k); // 加上k个硬币
                    }
                }
            }
        }

        return dp[coinZhonglei][amount] == INF ? -1 : dp[coinZhonglei][amount];
    }
}

class Solution {
    /**
    一看就是完全背包问题
    二维，第一维=是金币编号，第二维是剩余金额
    注意，总金额也需要刚好凑成
     */
    public int coinChange(int[] coins, int amount) {
         // 完全背包
        int n = coins.length;
        int INF = 0x3f3f3f3f;

        // 第一维表示编号，第二位表示总的金额
        // dp表示在j金额下，从1～i硬币下的最少个数
        int[][] dp = new int[n+1][amount+1];

        // 边界
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= amount; j++) {
                for (int k = 0; k * coins[i-1] <= j; k++) {
                    dp[i][j] = Math.min(dp[i-1][j-k*coins[i-1]] + k, dp[i][j]);
                }
            }
        }

        return dp[n][amount] == INF ? -1 : dp[n][amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        // 动态规划
        // 这是个完全背包问题，然后题目问的是恰好凑成，而不是<=即可
        int n = coins.length;

        int[][] dp = new int[n + 1][amount + 1];

        // 边界
        // 00表示金额为0且不选择任何硬币的时候，为1
        dp[0][0] = 1;

        for (int i = 1; i <= coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                // 注意这里需要从0开始，代表不选
                for (int k = 0; k * coins[i-1] <= j; k++) { 
                    dp[i][j] += dp[i-1][j-k*coins[i-1]];
                }
            }
        }

        return dp[n][amount];
    }
}

// 一维优化
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
				// 哨兵
        int[] dp = new int[amount+1];
				// 边界
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
          	// 完全，优化的一维从左往右，注意j从coins[i-1]开始，注意是i-1
            for (int j = coins[i-1]; j <= amount; j++) {
                dp[j] += dp[j-coins[i-1]];
            }
        }

        return dp[amount];
    }
}

class Solution {
    /**
    使用dp，状态压缩
    题目中，target的位数最多25位，所以可以用state来表示
     */
    public int minStickers(String[] stickers, String target) {
        int tLen = target.length();
        int mask = 1 << tLen;

        // 表示到达这个状态，需要的最小的贴纸
        int[] dp = new int[mask];

        // 边界
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        // 对每一个状态，注意，从0开始，因为要从这个状态，转移到另外一个状态
        for (int state = 0; state < mask; state++) {
            // 如果是最大值，那就证明没有到达过这个状态，所以这个状态也不能接下去
            if (dp[state] == Integer.MAX_VALUE) {
                continue;
            }
            
            // 每一个状态，经过每一张贴之后，会变成新的状态，然后取新的状态的最小
            for (String sticker: stickers) {
                int nextState = state;

                // 对贴纸的每一个字符，看看target中有没有，再看看是否已经被选上了
                for (int i = 0; i < sticker.length(); i++) {
                    // 看target中是否已经有了

                    for (int j = 0; j < target.length(); j++) {
                        // target中有，并且还没有占位，那么占上
                        if (target.charAt(j) == sticker.charAt(i) && ((1 << j) & nextState) == 0) { // 注意这里面比较的是新的state
                            nextState |= (1 << j);
                            break; // 有一个就可以到下一个单词了
                        }
                    }
                }

                dp[nextState] = Math.min(dp[state] + 1, dp[nextState]);
            }
        }



        return dp[mask - 1] == Integer.MAX_VALUE ? -1 : dp[mask - 1];
    }
}

class Solution {
    public int countArrangement(int n) {
        // 考虑到这个整数最大为15，所以可以用一个整数，状态压缩
        int mask = 1 << n;

        // 第一维度代表 0～n的整数
        // 前i个整数，在state方案下，有多少种数量
        int[][] dp = new int[n + 1][mask];

        // 边界
        dp[0][0] = 1;

        // 对于前1～n个数字
        for (int i = 1; i <= n; i++) {
            // 在每一此前i个数字下，需要遍历所有的statestate
            // 该state的状态修改，是：每一个1～k的数字没选择时候状态的dp和
            // 所以下面遍历每一个状态，然后遍历每一个k，去求和
            for (int state = 0; state < mask; state++) {
                for (int k = 1; k <= n; k++) {
                    // 要求前面未选k的时候状态和
                    // 首先需要该k在i位置满足优美排列要求
                    // 其次，该k在该状态是存在的，那么我才能是前面未选k的状态的和
                    if (!(k % i == 0 || i % k == 0)) { continue; }
                    if (((state >> (k-1)) & 1) == 0) { continue; }

                    dp[i][state] += dp[i-1][state & ~(1 << (k-1))];
                }
            }
        }
        
        return dp[n][mask-1];
    }
}

/**
    * 下一个最大元素，使用单调栈
    */
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 现将nums2倒序遍历，越底下越大
        Deque<Integer> stack = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = nums2.length-1; i >= 0; i--) {
            int num = nums2[i];
            while (!stack.isEmpty() && stack.peek() <= num) {
                stack.pop();
            }

            map.put(num, stack.isEmpty() ? -1 : stack.peek()); //  nums2中当前的值的下一个最大值
            stack.push(num);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }

        return ans;
    }
}

/**
    * 下一个更大的元素，使用单调栈
    * 注意，此处一个数组，存下标，本来数组中无重复元素的话，可以map存储值，但是此处只能存下标
    * 因为循环，可以把数组拉成2倍，但是此处不需要拉伸，直接循环取模
    */
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] ans = new int[nums.length];

        Arrays.fill(ans, -1);
        int n = nums.length;
        for (int i = 0; i < 2 * n - 1; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                ans[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);
        }

        return ans;
    }
}

/**
* 是有后面的大小的问题，可考虑单调栈
*/
class Solution {
  public boolean find132pattern(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>();

    int numsk = Integer.MIN_VALUE;
    // numsk 是ijk，numsk是中间第二大的那个值
    // 从后往前遍历
    // numsk看作是所有出栈元素中最大的，因为出栈元素（单调递减排，小于当前num的要出栈），所以出栈元素的话，栈里面肯定有比他大的numsj（而且j下标肯定是在k前面）
    for (int i = nums.length-1; i >= 0; i--) {
      // 如果此时找到一个nums[i] < numsk
      // 则因为从后往前i<j<k，且numsi < numsk < numsj
      if (nums[i] < numsk) { return true; }
      while (!stack.isEmpty() && stack.peek() < nums[i]) {
        numsk = Math.max(numsk, stack.pop());
      }
      stack.push(nums[i]);
    }

    return false;
  }
}

/**
* 使用单调栈，存下标
* 注意此处从后往前判断的时候，不存在需要存下标n
* 以及相等的时候，若下标小，算其逻辑小于
*/
class Solution {
  public long subArrayRanges(int[] nums) {
    Deque<Integer> minStack = new ArrayDeque<>();
    Deque<Integer> maxStack = new ArrayDeque<>();
    int n = nums.length;
    int[] minLeft = new int[n];
    int[] maxLeft = new int[n];
    int[] minRight = new int[n];
    int[] maxRight = new int[n];

    for (int i = 0; i < nums.length; i++) {
      int num = nums[i];
      while (!minStack.isEmpty() && nums[minStack.peek()] > num) {
        minStack.pop();
      }
      minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
      minStack.push(i);

      while (!maxStack.isEmpty() && nums[maxStack.peek()] <= num) {
        maxStack.pop();
      }
      maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
      maxStack.push(i);
    }

    minStack.clear();
    maxStack.clear();
    for (int i = nums.length-1; i >= 0; i--) {
      int num = nums[i];
      while (!minStack.isEmpty() && nums[minStack.peek()] >= num) {
        minStack.pop();
      }
      minRight[i] = minStack.isEmpty() ? n : minStack.peek();
      minStack.push(i);

      while (!maxStack.isEmpty() && nums[maxStack.peek()] < num) {
        maxStack.pop();
      }
      maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
      maxStack.push(i);
    }

    long ans = 0;
    for (int i = 0; i < n; i++) {
      ans += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
      ans -= (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
    }

    return ans;
  }
}

/**
* 使用单调栈
* 单调递减排，然后若当前的大于栈顶，则证明可以接雨水
*/
class Solution {
  public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int ans = 0;

    for (int i = 0; i < height.length; i++) {
      while (!stack.isEmpty() && height[i] > height[stack.peek()]) { // 单调递减排
        int top = stack.pop();
        if (stack.isEmpty()) {  // 如果空了，接不了
          break;
        }

        int left = stack.peek(); // 此时left top i三个能接雨水
        int length = Math.min(height[left], height[i]) - height[top];
        int width = i - left - 1;
        ans += width * length;
      }
      stack.push(i);
    }

    return ans;
  }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 使用单调栈，找到两边分别第一个小于heights[i]的下标
        // 所以这是一个从左到右，递增；从右到左，递减。
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i]) {
                stack.pollLast();
            }

            left[i] = stack.isEmpty() ? -1 : stack.peekLast();
            stack.offerLast(i);
        }

        stack.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i]) {
                stack.pollLast();
            }

            // 注意这里的哨兵，如果为空的话，下标为n
            right[i] = stack.isEmpty() ? n : stack.peekLast();
            stack.offerLast(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
        }

        return ans;
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 使用单调栈，找到两边分别第一个小于heights[i]的下标
        // 所以这是一个从左到右，递增；从右到左，递减。
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];

        // 边界
        // 注意，如果将上一次代码的从右往左的单调栈也放到这一次里面，那么首先需要所有的right初始值为nn
        // 然后是在while里面赋值
        // 然后注意一下等号的情况，此处虽然有问题，但是右边的会修正，所以无所谓
         Arrays.fill(right, n);

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i]) {
                right[stack.peekLast()] = i;
                stack.pollLast();
            }

            left[i] = stack.isEmpty() ? -1 : stack.peekLast();
            stack.offerLast(i);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1));
        }

        return ans;
    }
}

class Solution {
    public int maximalRectangle(char[][] matrix) {
        // 可以归纳为84的变种
        int row = matrix.length;
        int col = matrix[0].length;
        int ans = 0;

        if (row == 0) {
            return ans;
        }

        int[][] heightss = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    heightss[i][j] += i > 0 ? heightss[i-1][j] + 1 : 1;
                } else {
                    heightss[i][j] = 0;
                }
            }
        }

        for (int[] heights: heightss) {
            Deque<Integer> stack = new ArrayDeque<Integer>();
            int[] right = new int[col];
            int[] left = new int[col];

            for (int i = 0; i < col; i++) {
                // 从左往右，递增，需要找到第一个小于当前i的值的下标
                while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i]) {
                    stack.pollLast();
                }

                left[i] = stack.isEmpty() ? -1 : stack.peekLast();
                stack.offerLast(i);
            }

            stack.clear();
            for (int i = col - 1; i >= 0; i--) {
                while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i]) {
                    stack.pollLast();
                }

                right[i] = stack.isEmpty() ? col : stack.peekLast();
                stack.offerLast(i);
            }
            
            for (int i = 0; i < col; i++) {
                ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
            }
        }

        return ans;
    }
}