原题如下：

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

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这是一道非常经典的题目，有多种算法可以解决，在这里我们讨论其中的三种算法。

NO.1 第一种方法可以称为穷举法，尝试所有的可能，这也是最容易想到的方法

int maxSubArray(int* nums, int numsSize){
    int maxsum=nums[0];
    int somesum;
    for(int i=0;i<numsSize;i++){
        for(int j=i;j<numsSize;j++){
            somesum=0;
            for(int k=i;k<=j;k++)
                somesum+=nums[k];

                if(somesum>maxsum)
                    maxsum=somesum;
        }
    }
    return maxsum;
}
    

但是这种方法的缺点也是显而易见，三重循环，在我们将这样的代码输入leetcode中时会出现超时的提示，但是按照原理来说，该代码是没有问题的。三重循环所消耗的时间太长，那我们来想办法撤去一个for循环。

NO.2

int maxSubArray(int* nums, int numsSize){
    int maxsum=nums[0];
    int somesum;
    for(int i=0;i<numsSize;i++){
        somesum=0;
        for(int j=i;j<numsSize;j++){
            somesum+=nums[j];
            if(somesum>maxsum)
                maxsum=somesum;
        }
    }
    return maxsum;
}

观察第一种方法和第二种方法会发现第二种方法的更新最大值的代码段在for语句之中，这样就能很巧妙的减少一次循环，大家可以仔细体会。

NO.3接下来我们来看最后一种方法，虽然第二种方法已经减少了一次for循环，但是所消耗的时间还是很多，所以我们来介绍一种只需要一个for循环的方法

int maxSubArray(int* nums, int numsSize){
    int maxsum=nums[0];
    int somesum=0;
    for(int i=0;i<numsSize;i++){
        if(somesum<0) somesum=0;
        somesum+=nums[i];
        if(somesum>maxsum)
            maxsum=somesum;
    }
    return maxsum;
}

这种方法和第二种方法一样都是在一个for循环中进行最大值的更新，我们要对这上面的if(somesum<0) somesum=0;好好体会，当然了当我们没办法直接理解一个程序的时候，我们可以选择去举例然后带入程序，体会它的每一步的作用。第三种方法的好处就是只对数据进行一次扫描，只需要对数组中的数据进行一次读取和处理就无需再去记忆它了。

这就是算法的乐趣，一种题目有多种算法可以解决，而这多种方法里处理时间和思维又有着差别，值得我们去好好体会。