最長遞增子序列（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 < rig){
            int mid = (lef + rig) / 2;
            if (nums[mid] < target){
                lef = mid;
            }else rig = mid;
        }

        return rig;
    }
}

• 分析

維護(hù)一個(gè)最小遞增array（子序列）通過二分查找篩除壞值（比新插入值大）

利用二分查找優(yōu)化查詢

乘積的最大子數(shù)組（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 < n; i++){
            postive_dp[i] =  max(postive_dp[i-1] * nums[i], negative_dp[i-1] * nums[i], nums[i]);
            negative_dp[i] = min(postive_dp[i-1] * nums[i], negative_dp[i-1] * nums[i], nums[i]);
        }
        
        int res = Integer.MIN_VALUE;
        for (int postive_num : postive_dp){
            res = Math.max(res, postive_num);
        }
        return res;
    }

    private int max(int val1, int val2, int val3){
        val2 = Math.max(val2, val3);
        return Math.max(val1, val2);
    }

    private int min(int val1, int val2, int val3){
        val2 = Math.min(val2, val3);
        return Math.min(val1, val2);
    }
}

• 分析

因?yàn)閚um有<正，負(fù)>兩種狀態(tài)，即使前值算出來很小 但通過乘負(fù)數(shù)可以將大局逆轉(zhuǎn)吧

所以維護(hù)最大正數(shù)和最小負(fù)數(shù)兩個(gè)dp，都是潛力

同樣也可以優(yōu)化內(nèi)存， 因?yàn)橹灰蕾嚽耙粋€(gè)狀態(tài)

分割等和子集（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<Integer> stack = new ArrayDeque<>();
        stack.push(-1); // 避免第一個(gè)數(shù)值是左括號， 無值彈出
        int res = 0;

        for (int i = 0; i < n; i++){
            if (s.charAt(i) == '('){
                stack.push(i);
            }else{
                stack.pop();
                if (stack.isEmpty()){
                    stack.push(i);
                }else{
                    res = Math.max(res, i - stack.peek());
                }
            }
        }

        return res;
    }
}

• 分析

沒什么好想法，就用棧了

java 里棧的優(yōu)化似乎不好，不如雙端隊(duì)列