淘先锋技术网

首页 1 2 3 4 5 6 7

leetcode 53:最大子序和

方法1：暴力解决方式

int maxSubArray(std::vector<int>&nums){
   int max=nums[0];
   int sum;
   for(int i=0;i<nums.size();i++){
      for(int j=i;j<nums.size();j++){
         sum=0;
         for(int k=i;k<=j;k++){
             sum+=nums[k];
             if(sum>max)
                 max=sum;
         }
      }
   }
   return max;
}

暴力解决方式的时间复杂度是O(n^3),在leetcode上执行时会超出时间限制

方法2：在暴力解决方式上稍加改进

int maxSubArray(std::vector<int>&nums){
   int max=nums[0];
   int sum;
   for(int i=0;i<nums.size();i++){
      sum=0;
      for(int j=i;j<nums.size();j++){
          sum+=nums[j];
          if(sum>max)
               max=sum;
      }
   }
   return max;
}

这种方法的时间复杂度为O(n^2)在leetcode可以通过

方法3：分治方法

分治法举例

int MCS(std::vector<int>&nums,int s,int t){
    int maxLeft,maxRight,maxLeftBorder,maxRightBorder;
    int center;
    int temp;
    if(s==t)return nums[s];
    center=(s+t)/2;
    maxLeft=MCS(nums,s,center);
    maxRight=MCS(nums,center+1,t);
    
    maxLeftBorder=nums[center];
    temp=nums[center];
    for(int j=center-1;j>=s;j--){
        temp+=nums[j];
        if(temp>maxLeftBorder)maxLeftBorder=temp;
    }

    maxRightBorder=nums[center+1];
    temp=nums[center+1];
    for(int j=center+2;j<=t;j++){
        temp+=nums[j];
        if(temp>maxRightBorder)maxRightBorder=temp;
    }
    return std::max(std::max(maxLeft,maxRight),maxRightBorder+maxLeftBorder);
}

int maxSubArray(std::vector<int>&nums){
   int s=0;
   int t=nums.size()-1;
   return MCS(nums,s,t);
}

分治法的时间复杂度为O(nlgn)

方法四：动态规划

考虑一个这样的序列：-2 1 -3 4 -1 2 1 -5，4
a[i]表示这个序列的第 i 个元素，dp[i]表示最后一个元素是a[i]的最大连续和
dp[0] : a[0] ; ( -2 )
dp[1] : max(dp[0] + a[1] , a[1]) ; ( 1 )
dp[2] : max(dp[1] + a[2] , a[2]) ; ( -2 )
dp[3] : max(dp[2] + a[3] , a[3]) ; ( 4)
dp[4] : max(dp[3] + a[4] , a[4]) ; ( 3 )

dp[5] : max(dp[4] + a[5] , a[5]) ; ( 5 )
dp[6] : max(dp[5] + a[6] , a[6]) ; ( 6)
dp[7] : max(dp[6] + a[7] , a[7]) ; ( 1 )

dp[8]:max(dp[7]+a[8],a[8]);(5)

数组dp中最大值为6，即为结果

int maxSubArray(std::vector<int>&nums){
   int max=nums[0];
   int sum=nuns[0];
   for(int i=1;i<nums.size();i++){
       nums[i]=std::max(nums[i-1]+nums[i],nums[i]);
       if(max<nums[i])max=nums[i];
   }
   return max;
}

动态规划的时间复杂度为O(n)

网上看过一个更精妙的写法：

int maxSubArray(std::vector<int>& nums) {
    int max=nums[0];
    int sum=0;
    for(int i=0;i<nums.size();i++)
    {
        sum+=nums[i];
        if(max<sum)
            max=sum;
        if(sum<0)  //即如果sum<0时，sum+nums[i]和num[i]的肯定为nums[i] 
            sum=0;
    }
    return max;
}