Leetcode 053 题
Difficulty:Easy
Tag: Dynamic Programming, Divide and Conquer
题目
题目原址：https://leetcode.com/problems/maximum-subarray/?tab=Description
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.
思路1-动态规划
利用动态规划的思想，设 $dp[i]$ 为 数组 $nums[0..i]$ 的元素和的最大值。
所以，$dp[i] = \max(dp[i - 1] + nums[i], dp[i - 1])$
代码1-动态规划
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0;
int MAX = INT_MIN;
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
MAX = max(sum, MAX);
if(sum < 0) sum = 0;
}
return MAX;
}
};
思路2-分治
将数组分而治之，会有三种情况
假设数组 nums[left, right] 存在最大区间，mid = (left + right) /2
情况1： 最大值在 nums[left, mid - 1]里
情况2： 最大值在 nums[mid + 1, right]里
情况3： 最大值横跨三个部分，即nums[left, mid -1]的最大值加上nums[mid + 1, right]的最大值，再加上mid为最终的值。
代码2-分治
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int MAX = INT_MIN;
return divide(nums, 0, nums.size() - 1, MAX);
}
int divide(vector<int>& nums, int left, int right, int dmax)
{
//base
if(left > right) return dmax;
//处理情况1和2
int mid = left + (right - left) / 2;
//获得区间 nums[left, mid -1]的最大值
int lmax = divide(nums, left, mid - 1, dmax);
//获得区间 nums[mid + 1, right]的最大值
int rmax = divide(nums, mid + 1, right, dmax);
dmax = max(lmax, dmax);
dmax = max(rmax, dmax);
//处理情况3
int sum = 0;
int mlmax = 0;
for(int i = mid - 1; i >= left; i--)
{
sum += nums[i];
mlmax = max(sum, mlmax);
}
sum = 0;
int mrmax = 0;
for(int i = mid + 1; i <= right; i++)
{
sum += nums[i];
mrmax = max(sum, mrmax);
}
//返回三种情况中最大的
dmax = max(dmax, mlmax + nums[mid] + mrmax);
return dmax;
}
};