LeetCode 53.最大子序和（详解）

53.最大子序和

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

示例:

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

解题思路

因为数列中的数存在负数，而现在我们要求最大子列和，所以肯定要尽可能避免带上负数，而且最大子列和的第一位和最后一位肯定不是负数，要是负数那岂不是比初始值0还要小，也就不可能找到目标值。所以要判断第一个加上的数是否为负数，而在子列中部则可以存在负数，但是包括此负数在内的前n项和也要大于0，不然还不如不加呢。

实现代码

int maxSubArray(int* nums, int numsSize){
    int temp=0;
    int max = INT_MIN;   //INT_MIN表示最小的整数

    if(numsSize==0){
        return NULL;
    }

    for(int i=0;i<numsSize;i++){
        temp += nums[i];
        if(temp>max){      //判断是否大于已知的max
            max = temp;
        }
        if(temp<0){         //判断是否小于0，如果小于0就抛弃掉之前相加的结果，继续朝后加
            temp = 0;
        }
    }
    return max;
}