Leetcode題解 - 53. Maximum Subarray

2019-11-06 06:12:21

字體：大中小

來源：轉載

供稿：網友

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.

鏈接

解法一

枚舉法，找到每個元素開始的前綴和，逐個比較找出最大的即為前綴和，結果超時，O(n^2)

int maxSubArray(vector<int>& nums) { int max_sum = nums[0]; for (int i = 0; i < nums.size(); i++) { int tmp=0; for(int j=i;j<nums.size();j++){ tmp=tmp+nums[j]; max_sum=max(max_sum,tmp); } } return max_sum; }

解法二

分治法，最大連續子序列可能存在的三個區間： 1. 完全在nums[left, mid-1] 2. 完全在nums[mid+1, right] 3. 包含 nums[mid],然后向左右擴展最后比較左子序列、右子序列和中間序列，得到最大和。時間復雜度O(nlogn)，通過

int maxSubArray(vector<int>& nums) { return divide(nums, 0, nums.size()-1);}int divide(vector<int>& nums, int left, int right) { if (left == right) return nums[left]; if (left+1 == right) return max(nums[left]+nums[right], max(nums[left], nums[right])); int mid = (left+right)/2; int left_max = divide(nums, left, mid-1); int right_max = divide(nums, mid+1, right); // 求中間連續子序列的最大和 int mid_max = nums[mid]; // 向左擴展 int temp = mid_max; for (int i = mid-1; i >= left; i--) { temp += nums[i]; mid_max = max(temp, mid_max); } // 向右擴展 temp = mid_max; for (int j = mid+1; j <= right; j++) { temp += nums[j]; mid_max = max(temp, mid_max); } return max(mid_max, max(left_max, right_max));}