small class : 9/5 （not done yet!!）

Q1: maximum subarray的各种follow up!
 basic maximum subarray question:

1. Given an integer array, find the max subarray sum.

eg. {1, 3, -5, 4, 2, -1} → 6

一维dp， 维持一个Local max, 和global_max， 每次的结果在这两个里面取最大值。

int maxSub(vector<int> &input) {

        if (input.size() == 0) return 0;

        int local = input[0];

        int gmax = local;

        for (int i = 1; i < input.size(); i++) {

            local = max(local + input[i], input[i]);

            gmax = max(gmax, local);

        }

        return gmax;

 }

basic的这个题目很简单

1.1 connect the array to be a circle.

eg. {1, 3, -5, 4, 2, -1} → 9

如果这个array的首尾是相连的，如何求maximum sum呢？

这个题目体现了一种对于circular array进行处理的方法， 一般对于circular array可以先把整个array的总和求出来，减去其中任意一段的和，就可以得到两头的元素组成的和。这种思想下，解决这个题目是最简单的方法：

M1： step1: find the maximum subarray sum

step2: find the minimal subarray sum and the total sum of the whole array, get the result of the total - minimal sum

step3: get the larger result.

 int maxSub(vector<int> &input) {

        if (input.size() == 0) return 0;

        int local = input[0];

        int gmax = local;

        for (int i = 1; i < input.size(); i++) {

            local = max(local + input[i], input[i]);

            gmax = max(gmax, local);

        }

        return gmax;

    }

    int minSub(vector<int> &input) {

        if (input.size() == 0) return 0;

        int local = input[0];

        int gmin = local;

        for (int i = 1; i < input.size(); i++) {

            local = min(local+input[i], input[i]);

            gmin = min(local, gmin);

        }

        return gmin;

    }

int main(int argc, const char * argv[]) {

    // insert code here...

    std::cout << "Hello, World!\n";

    Solution s;

    int input[6] = {1,3,-5,4,2,-1};

    vector<int> nums(input, input+6);

    int gmax = s.maxSub(nums);

    int tmp1 = s.minSub(nums);

    int sum = 0;

    for (int n : nums) {

        sum += n;

    }

    gmax = max(gmax, sum - tmp1);

    return 0;

}

这种circular的数组，有一种错误的思路，from left to right get the maximum sum of each index and from right to left get the maximum sum of each index, then find the maximum total sum of left[i] + right[i-1];

这种方法看起来是可行的，但是其实是错的，因为前面一部分和后面一部分最大subsum之和可能不是连续的，所以这样的解法是错误的。

1.2 Assume the array is not circular, given an integer k, the subarray should at least

have k elements, k > 0 && k <= arr.length.

这个题目在basic的基础上的变化是，之前那个题目subarray构成的元素个数是 >= 1， 但是现在的构成个数是 >= k, 其实这个follow up想法是类似的，也是用dp来解题，之前的dp思想是： 

dp[i] = max(dp[i-1] + input[i], input[i]); 但是现在必须是至少k个元素了， 肯定是不能仅仅input[i]，应该是sum[k]。

主要思想： sliding window (控制K)+ presum

 int maxSub(vector<int> &input, int k) {

        vector<int> M(input.size(), 0);

        int left = 0;

        int right = k-1;

        int sum = 0;

        for (int i = left; i <= right; i++) {

            sum += input[i];

        }

        M[right] = sum;

        int gmax = M[right];

        for (int i = right+1; i < input.size(); i++) {

            sum = sum - input[left] + input[i];

            M[i] = max(sum, input[i] + M[i-1]);

            left++;

            gmax = max(gmax, M[i]);

        }

        return gmax;

    }

Q2. 2. Given two list of intervals, each interval has a start and an end time.

Within the same list, the intervals does not have any intersection.

Find the intersection intervals of these two lists.

eg.

[1, 4], [6, 10], [11, 12]

[2, 3], [5, 7], [9, 15]

The intersections are:

[2, 3] [6, 7] [9, 10] [11, 12]

这个题目跟Leetcode上面的interval的那两题不同，这个题目有两个Interval的数组需要merge, 而leetcode上面的题目其实只相当于一个interval数组Merge, 感觉两种题目有各自的考点，Leetcode上面考的是连续merge的算法，而这个题目考的是 如何构建代码使得代码看起来简洁易懂而且不罗嗦。