44.哀家要长脑子了！

1.300. 最长递增子序列 - 力扣（LeetCode）

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        
        if(n == 0) return 0;

        vector<int> dp(n, 1);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < i; j++)
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j]+1);
        return *max_element(dp.begin(), dp.end());        
    }
};

对于数组中的每一个元素，可以假设它至少构成长度为1 的递增子序列（即自身）。当nums[j]大于nums[i]的时候，可以将nums[j] 加入到以nums[i] 为结尾的递增子序列中。

2.34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution {
public:
    int binsearch(vector<int> nums, int target) {
        int l = 0, r = nums.size() - 1;
        while(l <= r) {
            int mid = l + (r-l)/2;
            if(nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int st = binsearch(nums, target);
        if(st == nums.size() || nums[st] != target) 
            return {-1, -1};
        int en = binsearch(nums, target+1) - 1;
        return {st, en};
    }
};

 二分 一看就是二分。

3.744. 寻找比目标字母大的最小字母 - 力扣（LeetCode）

class Solution {
public:
    int binsearch(vector<char> nums, char target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    char nextGreatestLetter(vector<char>& letters, char target) {
        int res = binsearch(letters, target);
        if(res == letters.size() || letters[res] < target)
            return letters[0];
        return letters[res];
    }
};

注意，binsearch函数中是nums[mid] <= target

4.2529. 正整数和负整数的最大计数 - 力扣（LeetCode）

class Solution {
public:
    int binsearch(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right-left) / 2;
            if(nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
    int maximumCount(vector<int>& nums) {
        int neg = binsearch(nums, 0);
        int pos = (int)nums.size() - binsearch(nums, 1);
        return pos > neg ? pos : neg;        
    }
};

不包括0，就从1开始找就好了啊