暑假一定要好好刷题-皿- 为了不996

Maximum Subarray

int maxSubArray(vector<int>& nums) {
    int add =nums[0];
    int max = nums[0];
    for(int i=1;i<nums.size();i++){
        if(add<0) {
            add = nums[i];
            if(add>max) max=add;
        }
        else{
            add+=nums[i];
            if(add>max) max=add;
        }
    }
    return max;
}

Pay attention to boundary contidion. When initialize a result to 0 and compare bigger or smaller, need to consider the 0 initialized compared with positive & negtive value -> best way: choose the first element to be initialized value and begin iteration with num1.
Always consider when there is no element or 1 element in input.
Other methods:

1. sum up array from left to right and find largest difference between these sums.
2. divide and conquer
   choose the largest between max_left, max_right and sum of left and this element and right.

Majority Element

1. hashmap: time O(n), space O(n)
2. brute force: time O(n^2) space O(1)
3. sort (interesting): time O(n^2) space O(1)
4. divide and conquer(not good): left majority == right majority or recount
   Time O(nlogn) space O(logn)【not O(1)】
5. Boyer-Moore Voting Algorithm(very interesting): somewhat like maximum subarray, begin with index 0, add 1 for same number, minus 1 for different number, when go to 0, change to a new number. Finally the majority will get positive result.
   Time O(n), space O(1)

Kth Largest Element in an Array

1. Use heap.
   A brilliant opinion:
   不应该用“最大堆”、“最小堆”来概括这两种方法，因为 求第 k 大 可以转换为 求第 n - k + 1 小，根据不同情况进行优化，两者都可以用最大堆和最小堆实现。
   对所有数据建堆。如果 k 接近 n，建最大堆；如果接近 1，建最小堆。目标都是使 pop 次数最小。
   建大小为 x 的堆，其中 x 可以为 k，也可以为 n - k。同理最大最小堆均可。无论最大还是最小，目标都是把 n - x 个元素排除掉。堆建得越小，建堆用时 O(x) 越小，排除用时 O((n-x)logx) 越大。
   考虑这一点后，两种方法最好的情况都是 O(n)，都是 k 接近 1 或者 n 的时候。最坏都是 O(nlogn)，都是 k 接近 n/2 的时候。空间复杂度方面，如果允许在数据上直接建堆，那前者复杂度就是 O(1)，否则后者好于前者。
2. Use partition in quicksort