今天的題單：

• Maximum Subarray

• Insert Interval

53. Maximum Subarray

給一個數字 array，找出 subarray 總和中的最大值。

Examples

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Attempt 1：暴力解， O(n^2) time

建立一個 2D array， arrary[i][j] 紀錄 index i ~ index j 的和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        int max_sum = INT_MIN;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j <= i; j ++) {
                if (i == j) {
                    dp[j] = nums[i];
                } else {
                    dp[j] = dp[j] + nums[i];
                }
                max_sum = max(max_sum, dp[j]);

            }
        }
        return max_sum;

    }
};

Attempt 2：用 Greedy approach，O(n) time

觀察 array 中數字依序相加的過程會發現如果從 index i ~ index j 的總和是負數，表示從 i 開始往後加的總和一定都小於從 j+1 開始加的總和，所以遇到這種情況時可以捨棄前面的總和，直接從 j+1 開始往後加。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = INT_MIN;
        int sum = 0;

        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            max_sum = max(max_sum, sum);

            if (sum < 0) {
                sum = 0;
            }
        }
        return max_sum;
    }
};

57. Insert Interval

Examples

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

思路﹔假設要插入的 new interval 是 [a, b]。先找到要 insert 的位置。再往後看判斷 [a, b] 與那些 interval 有重疊，把這些重疊的 interval 結合起來。

• 插入的 interval 的位置前面的 interval 尾端都小於 a

• 進入合併階段的時候，起頭小於 b 的 interval 會與 [a, b] 重疊，需要合併

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> new_intervals;
        vector<vector<int>>::iterator it = intervals.begin();
        vector<int> new_form_interval(newInterval);

        while (it != intervals.end() && new_form_interval[0] > (*it)[1]) {
            new_intervals.push_back(*it);
            it++;
        }

        // merge
        while (it != intervals.end() && new_form_interval[1] >= (*it)[0]) {
            new_form_interval[0] = min(new_form_interval[0], (*it)[0]);
            new_form_interval[1] = max(new_form_interval[1], (*it)[1]);
            *it++;
        }

        new_intervals.push_back(new_form_interval);

        while (it != intervals.end()) {
            new_intervals.push_back(*it);
            it++;
        }

        return new_intervals;
    }
};