[LeetCode] 53. Maximum Subarray

轉自LeetCode

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

<Solution>

這題希望我們可以用 O(n) 以及 divide and conquer 兩種做法來解

先來看 O(n) 的解法

仔細觀察一下，用題目給的例子 [-2, 1, -3, 4, -1, 2, 1, -5, 4]

一開始是 [-2]，sum = -2

增加一個元素 [-2, 1]，sum = -1 < 1

這代表一件事，從 -2 開始的 subarray 的和，不會比從 1 開始的 subarray 的和還要大

因此可以不用再看從 -2 開始的 subarray

例如 : [-2, 1, -3] => sum = -4，[1, -3] => sum = -2

利用這個特性，可以在一次歷遍就完成 => O(n)

code 如下

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

view raw maxSumOfSubarry_1.cpp hosted with ❤ by GitHub

再來看 divide and conquer 的解法 (參考資料)

時間複雜度會是 O(nlong)

想法如下

• divide : 分左半和右半，以及 left 和 right 中間的 substring，三個部分

• conquer : 比較 leftMax，rightMax，midMax 誰最大

code如下

	class Solution {
	public:
	int maxSubArray(vector<int>& nums) {
	return divideAndConquer(0, nums.size()-1, nums);
	}
	int divideAndConquer(const int &left, const int &right, vector<int> &nums) {
	if(left >= right) {
	return nums[left];
	}
	int mid = (left + right) / 2;
	int leftMax = divideAndConquer(left, mid-1, nums);
	int rightMax = divideAndConquer(mid+1, right, nums);
	//> also need to check substring between left and right
	int midMax = nums[mid], tmpSum = nums[mid];
	//> go left
	for(int i = mid-1; i >= left; i--) {
	tmpSum += nums[i];
	midMax = max(midMax, tmpSum);
	}
	//> go right
	tmpSum = midMax;
	for(int i = mid+1; i <= right; i++) {
	tmpSum += nums[i];
	midMax = max(midMax, tmpSum);
	}
	//> return max
	return max(max(leftMax, rightMax), midMax);
	}
	};

view raw maxSumOfSubarry_2.cpp hosted with ❤ by GitHub