最长递增子序列（300）

class Solution {
    public int lengthOfLIS(int[] nums) {
        int res = 1;
        for(int num : nums){
            int idx = findLarge(nums, res, num);
            nums[idx] = num;
            if (idx == res) res++;   
        }
        
        return res;
    }

    private int findLarge(int[] nums, int rig, int target){
        int lef = -1;
        while (lef+1 

• 分析

维护一个最小递增array（子序列）通过二分查找筛除坏值（比新插入值大）

利用二分查找优化查询

乘积的最大子数组（152）

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] postive_dp = new int [n];
        int[] negative_dp = new int [n];

        postive_dp[0] = negative_dp[0] = nums[0];
        for(int i = 1; i 

• 分析

因为num有两种状态，即使前值算出来很小 但通过乘负数可以将大局逆转吧

所以维护最大正数和最小负数两个dp，都是潜力

同样也可以优化内存， 因为只依赖前一个状态

分割等和子集（416）

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num: nums){
            sum += num;
        }
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for (int num : nums){
            for (int subSum = target; subSum >= num; subSum--){
                dp[subSum] |= dp[subSum - num];
                if (dp[target]) return true;
            }
        }
        return false;
    }
}

• 分析

背包问题

最长有效括号(32)

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        Deque stack = new ArrayDeque();
        stack.push(-1); // 避免第一个数值是左括号， 无值弹出
        int res = 0;

        for (int i = 0; i 

• 分析

没什么好想法，就用栈了

java 里栈的优化似乎不好，不如双端队列