1. 暴力枚举
2. “聪明”枚举
3. 分治法
分：两个基本等长的子数组，分别求解T(n/2)
合：跨中心点的最大子数组合（枚举）O(n)
时间复杂度：O(n*logn)
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @return: A integer indicate the sum of max subarray 6 */ 7 int maxSubArray(vector<int> nums) { 8 // write your code here 9 int size = nums.size(); 10 if (size == 1) { 11 return nums[0]; 12 } 13 int *data = nums.data(); 14 return helper(data, size); 15 } 16 int helper(int *data, int n) { 17 if ( n == 1) { 18 return data[0]; 19 } 20 int mid = n >> 1; 21 int ans = max(helper(data, mid), helper(data + mid, n - mid)); 22 int now = data[mid - 1], may = now; 23 for (int i = mid - 2; i >= 0; i--) { 24 may = max(may, now += data[i]); 25 } 26 now = may; 27 for (int i = mid; i < n; i++) { 28 may = max(may, now += data[i]); 29 } 30 return max(ans, may); 31 } 32 };
4. dp（不枚举子数组，枚举方案）
dp[i]表示以a[i]结尾的最大子数组的和
dp[i] = max(dp[i-1]+a[i], a[i])
包含a[i-1]:dp[i-1]+a[i]
不包含a[i-1]:a[i]
初值：dp[0] = a[0]
答案：最大的dp[0...n-1]
时间：O(n)
空间：O(n)
空间优化：dp[i]要存吗？
endHere = max(endHere+a[i], a[i])
answer = max(endHere, answer)
优化后的空间：O(1)
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @return: A integer indicate the sum of max subarray 6 */ 7 int maxSubArray(vector<int> nums) { 8 // write your code here 9 int size = nums.size(); 10 if (size == 1) { 11 return nums[0]; 12 } 13 vector<int> dp(size); 14 dp[0] = nums[0]; 15 int ans = dp[0]; 16 for (int i=1; i<size; i++) { 17 dp[i] = max(dp[i - 1] + nums[i], nums[i]); 18 ans = max(ans, dp[i]); 19 } 20 return ans; 21 } 22 };
空间优化
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @return: A integer indicate the sum of max subarray 6 */ 7 int maxSubArray(vector<int> nums) { 8 // write your code here 9 int size = nums.size(); 10 if (size == 1) { 11 return nums[0]; 12 } 13 int endHere = nums[0]; 14 int ans = nums[0]; 15 for (int i=1; i<size; i++) { 16 endHere = max(endHere + nums[i], nums[i]); 17 ans = max(ans, endHere); 18 } 19 return ans; 20 } 21 };
5. 另外一种线性枚举
定义：sum[i] = a[0] + a[1] + a[2] + ... + a[i] i>=0
sum[-1] = 0
则对0<=i<=j：
a[i] + a[i+1] + ... + a[j] = sum[j] - sum[i-1]
我们就是要求这样一个最大值：
对j我们可以求得当前的sum[j],取的i-1一定是之前最小的sum值，用一个变量记录sum的最小值
时间：O(n)
空间：O(1)
1 class Solution { 2 public: 3 /** 4 * @param nums: A list of integers 5 * @return: A integer indicate the sum of max subarray 6 */ 7 int maxSubArray(vector<int> nums) { 8 // write your code here 9 int size = nums.size(); 10 if (size == 1) { 11 return nums[0]; 12 } 13 int sum = nums[0]; 14 int minSum = min(0, sum); 15 int ans = nums[0]; 16 for (int i = 1; i < size; ++i) { 17 sum += nums[i]; 18 ans = max(ans, sum - minSum); 19 minSum = min(minSum, sum); 20 } 21 return ans; 22 } 23 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5006447.html，如需转载请自行联系原作者
