LeetCode 53. Maximum Subarray [Easy] [C++] 解題筆記

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

EX:

        Input: [-2,1,-3,4,-1,2,1,-5,4],

        Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

想法:

        這題雖然是 easy 但我覺得定沒有那摸直覺簡單，值得多練習。這題主要有兩類作法，第一種

是 O(n) 的解法，因為我們目的是要找到總和最大的連續子陣列，因此可以遍歷整個 array 然後如果

當前位置的值大於加上前面累積的總和則更新總和為當前的值(重新開始累加，因為前面是負的可以丟掉)，

若否則直接累加，之後更新目前發現的最大總和值。

第二種作法是 O(nlogn) 的解法，是利用 divide and conquer 的概念(也類似 binary search)，將 array 不斷分割

為兩段更小的陣列 left 與 right，並分別在 left, right 中找他們個別最大的 subarray 值，但是這裡跟一般 divide and conquer

比較不一樣的是我們還必須要考慮到兩邊合在一起計算可能會比較大的 case，因此除了遞迴求解 left, right 的 subarray

還必須要從當前的 mid 分別向左右擴展看看是否能形成較大的 subarray 值，這個步驟最差會從中間遍歷到整個 array (整個 array 都是正數) 

因此複雜度是O(n) 加上會遞迴 O(logn) 次，因此整體時間複雜度會來到 O(nlogn)。

完整程式碼:

Complexity: O(n) time, O(n) space.

解法一(DP):

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        dp.at(0) = nums.at(0);
        int max_sum = dp.at(0);
        
        for (size_t i = 1; i < nums.size(); i++){
            dp.at(i) = nums.at(i) + ((dp.at(i-1) > 0)? dp.at(i-1) : 0);
            if (dp.at(i) > max_sum) {
                max_sum = dp.at(i);
            }
        }
        return max_sum;
    }
};

Complexity: O(n) time, O(1) space.

解法二:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_value = INT_MIN;
        int cur_sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            cur_sum = max(cur_sum + nums[i], nums[i]);
            max_value = max(max_value, cur_sum);
        }
        
        return max_value;
    }
};

Complexity: O(nlogn) time.

解法三(Divide and Conquer):

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return divideAndConquer(nums, 0, nums.size() - 1);   
    }
    int divideAndConquer(vector<int>& nums, int left, int right) {
        if (left >= right) { return nums[left]; }
        int mid = left + (right - left) / 2;
        int left_max = divideAndConquer(nums, left, mid - 1);
        int right_max = divideAndConquer(nums, mid + 1, right);
        int mid_sum = nums[mid];
        int cur_sum = mid_sum;
        for (int i = mid - 1; i >= left; i--) {
            cur_sum += nums[i];
            mid_sum = max(mid_sum, cur_sum);
        }
        cur_sum = mid_sum;
        for (int i = mid + 1; i <= right; i++) {
            cur_sum += nums[i];
            mid_sum = max(mid_sum, cur_sum);
        }
        
        return max(mid_sum, max(left_max, right_max));
    }
};