leetcode 53. Maximum Subarray

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

Example:

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

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

分析：求连续子数组的最大和

思路一：动态规划，定义的数组dp[], dp[i]表示以nums[i]结尾的最大子数组的和，计算dp[i + 1]时, dp[i + 1] = max(nums[i + 1], nums[i + 1] + dp[i])，如果dp[i]小于0,那么dp[i + 1] = nums[i + 1].

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int len = nums.size();
 5         vector<int> dp(len, 0);
 6         dp[0] = nums[0];
 7         int maxN = dp[0];
 8         for (int i = 1; i < len; i++) {
 9             dp[i] = max(nums[i], dp[i - 1] + nums[i]);
10             maxN = max(maxN, dp[i]);
11         }
12         return maxN;
13     }
14 };

思路二：分治法, 以包括或者不包括数组中间元素作为分治的条件。

 1 class Solution {
 2     int recursion(vector<int> nums, int l, int r) {
 3         if (l > r)
 4             return INT_MIN;
 5         if (l == r)
 6             return nums[l];
 7         int mid = ((r - l) >> 1) + l;
 8         //int mid = (l + r) / 2;
 9         int left = recursion(nums, l, mid - 1);
10         int right = recursion(nums, mid + 1, r);
11         int t = nums[mid], maxn = nums[mid];
12         for (int i = mid - 1; i >= l; i--) {
13             t += nums[i];
14             maxn = max(maxn, t);
15         }
16         t = maxn;
17         for (int i = mid + 1; i <= r; i++) {
18             t += nums[i];
19             maxn = max(maxn, t);
20         }
21         return max(max(left, right), maxn);
22     }
23 public:
24     int maxSubArray(vector<int>& nums) {
25         int len = nums.size();
26         if (len == 0)
27             return 0;
28         return recursion(nums, 0, len - 1);
29     }
30 };