题目
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
More practice:If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
分析
题目要求O(n)的算法，然而dp对我来说就是老大难，想了半天的我看到题目属于Easy的时候内心是崩溃的=_=。我觉得dp的关键在于找到具有无后效性的量。一开始我考虑使用dp[i]来表示前i-1个数字中答案，但是始终找不到推导方法。后来转念一想，如果dp[i]表示以nums[i]为结尾的数字串的最大的和，就能够简答得到推导了。然后再输出dp数组中的最大值即可。
实现一
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.empty()) return 0;
int dp[nums.size()];
dp[0] = nums[0];
for(int i=1; i<nums.size(); i++){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
}
int ans=INT_MIN;
for(int i=0; i<nums.size(); i++){
ans = max(ans, dp[i]);
}
return ans;
}
};
思考一
这道Easy的题想了好久，看来dp的路对我来说还是很漫长啊。而且发现了这道题有可以改进的地方：不需要使用dp数组保存每个位置的值，因为每次只用到了最后一个。所以可以只使用一个变量，降低空间复杂度。
另外题目还说要用分治法来完成。关键问题在于如何将两个区域归并。这个问题我看的题解上没有解决，其它选手的代码中好像也找不到使用分治法的。后来网上搜了一下，明白了：
- 两个区域合并时，只需要考虑跨越两个区域的子数组即可。这样只需要连接左边区域的以最后一个元素为结尾的最大子数组，以及右边区域的以第一个元素为开头的最大子数组即可（如果子数组的和为正的话）
实现二
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return solve(nums, 0, nums.size()-1);
}
private:
int solve(vector<int>& nums, int start, int end){
if(start>=end) return nums[start];
int mid = (start + end) / 2;
int lm = solve(nums, start, mid-1);
int rm = solve(nums, mid+1, end);
int mm = nums[mid];
int mm1 = INT_MIN, t = 0;
for(int i=mid-1; i>=start; i--){
t += nums[i];
mm1 = max(mm1, t);
}
mm += mm1>0 ? mm1 : 0;
int mm2 = INT_MIN; t = 0;
for(int i=mid+1; i<=end; i++){
t += nums[i];
mm2 = max(mm2, t);
}
mm += mm2>0 ? mm2 : 0;
return max(lm, max(mm, rm));
}
};
思考二
不得不说，通过这道题我对二分法有了更深的理解。另外这种题叫我一下子想我确实想不出来，还需要多多积累啊。
