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));}