Leetcode（53）-最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

这个题目有东西的，解法很多，有很多需要注意的地方，是一个很值得学习的题目。

思路一：暴力求解法。即一个一个的遍历，直到找到最大值为止。比如从第一个数，开始，加一个，加两个，……再从第二个数开始，加一个，加两个，……。这种算法，算法复杂度很高，O（n^2），所以一般不采用，只作为入门

int maxSubArray(vector<int>& nums)

{

    int max=nums[0],sum;

    for(int i=0;i<nums.size();i++)

    {

        sum=0;

        for(int j=i;j<nums.size();j++)

        {

            sum=sum+nums[j];

            if(sum>max)

            {

                max=sum;

            }

        }

    }

    return max;

}

思路二：用一层循环，从头开始遍历，如果这个值本身，比前面得到的值加上它还要大，证明我不再需要前面的那些数了，我只需要从这个数开始往后寻找更大的和了。当然如果不是这样，就把这个值加上，继续遍历

int maxSubArray(vector<int>& nums)

{

    int max=-INT_MAX,tmp=0;

    for(int i=0;i<nums.size();++i)

    {

        tmp=(tmp+nums[i])>nums[i]?tmp+nums[i]:nums[i];

        if(tmp>max)

            max=tmp;

    }

    return max;

}

要注意的地方是，一开始最大值max的初始化，不能初始化为0，因为这样会把前面的一些负数和给屏蔽掉，导致结果不对，所以应该初始化为第一个值nums[0]或者INT_MIN

思路三，也是最佳思路，利用了分治的思想，

1）分--将原数组拆分成两部分，每个部分再拆分成新的两部分......直到数组被分得只剩下一个元素；

　　　　2）治--每个小型的数组找最大子数组，只有一个元素的数组，解就是该元素；

　　　　3）合--将两个小型数组合并为一个数组，其中解有三种可能：（1）左边的返回值大（2）右边的返回值大（3）中间存在一个更大的子数组和；

这三种可能性中，中间存在的更大的子数组和的实现是重点，做法是每次从中间元素开始向两边开始相加，直到找到最大的，然后将左边值与右边值加起来，就是中间存在的大的子数组和。

int findmiddle(vector<int>&nums,int left,int right,int middle)

{

    int leftsum=nums[middle],rightsum=nums[middle+1];

    int sum=0;

    for(int i=middle;i>=left;i--)

    {

        sum+=nums[i];

        if(leftsum<sum)

        {

            leftsum=sum;

        }

    }

    sum=0;

    for(int j=middle+1;j<=right;j++)

    {

        sum+=nums[j];

        if(rightsum<sum)

        {

            rightsum=sum;

        }

    }

    return (leftsum+rightsum);

}

int helper(vector<int>& nums,int left,int right)

{

    if(left==right)

        return nums[left];

    int mid=(left+right)/2;

    int l=helper(nums,left,mid);

    int r=helper(nums,mid+1,right);

    int m=findmiddle(nums,left,right,mid);

    if ( l >= r && l >= m)

        return l;

    if ( r >= l && r >= m)

        return r;

    return m;

}

int maxSubArray(vector<int>& nums)

{

    return helper(nums,0,nums.size()-1);

}

这段程序在实现的过程中，我认为需要注意的是findmiddle函数中的leftsum和rightsum中的初始化问题，不能用0初始化，因为如果都是负数的话，会造成干扰，也不能用INT_MIN初始化，因为返回值是两个数的和，如果有一个没有被计算到，那么会造成错误，所以要用其中的第一个数来初始化。个人见解。

巴特西

Leetcode（53）-最大子序和

最新文章

热门文章