给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。
例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
连续子序列 [4,-1,2,1] 的和最大，为 6。
扩展练习:
若你已实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
很奇怪的是，百度了下分治法的时间复杂度为(n*logn),为啥它还要求用
这个算法求解的？
暴力解法就不说了
分治法解法：
思路：把数组分到足够小，然后求解最小子数组的解，即只有一个元素的数组，解就是该值，
然后结合起来组成最优解。
注意，左子数组和右子数组结合时，有最大值三种可能：左子数组最大值，右子数组最大值，中间
存在一个更大的值。
求解中间存在一个更大值的思路，从合成数组中部，分别往左右边延伸求左右边最大值，加起来即可。
//leetcode解答格式
class Solution {
public:
int maxSubArray(vector<int>& nums) {
return max_divide(0,nums.size()-1,nums);
}
//分治法
int max_divide(int l,int r,vector<int>& sub_nums)
{
if(l==r)
return sub_nums[l];
else
{
int m=(l+r)/2;
int l_max=max_divide(l,m,sub_nums);
int r_max=max_divide(m+1,r,sub_nums);
int m_max=mid_divide(l,r,sub_nums);
if(l_max>=r_max && l_max>=m_max)
return l_max;
else if(r_max>=l_max && r_max>=m_max)
return r_max;
else
return m_max;
}
}
//求中间最大值
int mid_divide(int l,int r,vector<int> &sub_nums)
{
int m=(l+r)/2;
int l_max=INT_MIN;
int r_max=INT_MIN;
int sum=0;
for(int i=m;i>=l;i--)
{
sum+=sub_nums[i];
if(sum>l_max)
{
l_max=sum;
}
}
sum=0;
for(int i=m+1;i<=r;i++)
{
sum+=sub_nums[i];
if(sum>r_max)
{
r_max=sum;
}
}
return (l_max+r_max);
}
};
动态规划:
线性扫描法，时间复杂度为O（n）
思路，设C(i)为以第i个元素结尾的最大和，
则C(i)=max{a(i),C(i-1)+a(i)}
并且当C(i-1)<0时，C(i)=a(i)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sub_max=INT_MIN;
int sum=0;
if(nums.size()==0) return 0;
for(unsigned int i=0;i<nums.size();i++)
{
sum+=nums[i];
if(sum>sub_max)
{
sub_max=sum;
}
if(sum<0)
{
sum=0;
}
}
return sub_max;
}
};
- 还没有人评论，欢迎说说您的想法！
客服
