当前位置：网站首页>【剑指offer】面试题42：连续子数组的最大和——附0x80000000与INT_MIN

【剑指offer】面试题42：连续子数组的最大和——附0x80000000与INT_MIN

2022-07-27 14:24:00 【Jocelin47】

在这里插入图片描述

方法一：暴力法(超时)

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
             int  n= nums.size();
             int res=-1e8;
             for(int i=0;i<n;i++){
    
                 int sum=0;
                 for(int j=i;j<n;j++) {
    
                     sum+=nums[j];
                     res=max(res,sum);
                 }
             }
             return res;
    }
};

方法二：

1、如果当前的nSum小于0的话，则可以把前面累加的都舍弃，只把nSum等于当前的nums[i]
2、把一个最小的数给记录最终最大值的结果。

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
        if( nums.size() == 0 ) 
            return 0;
        int nSum=0;
        //int greatSum=0x80000000;
        int greatSum=INT_MIN;//求最大值的结果给 最小的数
        for( int i=0; i<nums.size(); i++ )
        {
    
        	//当sum小于0时，就从下一个数重新开始
            if( nSum < 0 ) 
                nSum = nums[i];
            else
                nSum += nums[i];
            if(nSum > greatSum)
                greatSum=nSum;
        }
        return greatSum;
    }
};

方法三：动态规划

dp[i] 对应f(i)

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        int res=dp[0];
        
        for(int i = 1; i < nums.size() ; i++ ) {
    
            if( dp[i-1] <= 0 ) 
                 dp[i]=nums[i];
            else
               dp[i]=dp[i-1]+nums[i];
            res= max( dp[i], res);
        }
        return res;
    }
};