[sword finger offer] interview question 42: the maximum sum of continuous subarrays -- with 0x80000000 and int_ MIN

Method 1 ： Violence law ( Overtime )

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;
    }
};

Method 2 ：

1、 If the current nSum Less than 0 Words , You can discard all the previous accumulation , Only nSum Equal to the current nums[i]
2、 Record the result of the final maximum with a minimum number .

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
        if( nums.size() == 0 ) 
            return 0;
        int nSum=0;
        //int greatSum=0x80000000;
        int greatSum=INT_MIN;// The result of finding the maximum gives   Minimum number 
        for( int i=0; i<nums.size(); i++ )
        {
    
        	// When sum Less than 0 when , Just start over with the next number 
            if( nSum < 0 ) 
                nSum = nums[i];
            else
                nSum += nums[i];
            if(nSum > greatSum)
                greatSum=nSum;
        }
        return greatSum;
    }
};

Method 3 ： Dynamic programming

dp[i] Corresponding 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;
    }
};

attach ： Method 2 uses C/C++ Constant in ：

INT_MIN

INT_MIN In the header file limits.h in

because int Occupy 4 byte 32 position , According to the rules of binary coding ,INT_MAX = 2^31-1,INT_MIN= -2^31

INT_MAX + 1 = INT_MIN

INT_MIN - 1 = INT_MAX

abs(INT_MIN) = INT_MIN

INT_MAX + 1 < INT_MAX, INT_MIN - 1 > INT_MIN, abs(INT_MIN) < 0

0x80000000

0x80000000 Binary bit of
Original code 1000 0000 0000 0000 0000 0000 0000 0000
If the highest bit is the sign bit , Then for -0, But output int i = 0x80000000
i = -(2^31)