House Robber

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> sum (nums.size(), 0);
        sum[0] = nums[0];
        sum[1] = max(nums[1],nums[0]);
        for(int i=2;i<nums.size();i++){
            sum[i] = max(sum[i-2]+nums[i], sum[i-1]);
        }
        return sum[nums.size()-1];
    }
};

[2,1,1,2] => 并不是每隔一个加一就是最佳
最佳问题=>考虑DP=>思考循环的关联
对于一个nums[i]:

1. rob, 那么至此得到的总价是 sum[i-2]+nums[i];
2. 不rob, 得到的总价是sum[i-1].
   注意sum[0]和sum[1], 如果num[0]>num[1],那到1的时候没有必要rob，直接选择sum[0]。
   本来觉得不但要考虑i-1不能rob,还要考虑i+1不能rob，但是实际上可以留给i+1当前点考虑，rob nums[i+1]+sum[i-1];

---

House Robber II

0 and n-1 is adjacent, then they cannot be chosen both, therefore:

1. sum(0 - n-2)
2. sum(1 - n-1)
   calculate both same as in I.

---

Longest Increasing Subsequence

1. Traditional DP
   O(n2） O(n)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> len(nums.size(),1);
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) len[i] = max(len[i], len[j]+1);
            }
        }
        int ma = 0;
        for(int i=0;i<len.size();i++){
            ma = max(ma, len[i]);
        }
        return ma;
    }
};

2. DP with patient sorting

int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int i=0; i<nums.size(); i++) {
        auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
        if(it==res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
}

https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation