【LeetCode】最大子数组和

​🌠 作者：@阿亮joy.
🎆专栏：《阿亮爱刷题》
🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

👉最大子数组和👈

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

子数组和子序列的区别

• 子数组：数组中连续的一串，子数组的个数为N * (N + 1) / 2
• 子序列：数组中可以不连续的一串，子序列的个数为2 ^ N
• 注意：无论是子数组和子序列，元素的顺序都是原数组中的顺序

思路一

思路一是最暴力的解法，枚举所有的子数组，然后求出每个子数组的和，进而求出最大子数组和。该解法时间复杂度为O(N^3)，效率非常低效的一种解法。当numsSize很大时，就会超过时间的限制，无法通过所有的测试用例。

int maxSubArray(int* nums, int numsSize)
{
    int max = INT_MIN;//INT_MIN为整型最小值
    int L = 0;
    int R = 0;
    for(L = 0; L < numsSize; L++)
    {
        for(R = L; R < numsSize; R++)
        {
            //枚举从L到R的子数组
            int sum = 0;
            //sum为从L到R的累加和
            for(int i = L; i <= R; i++)
            {
                sum += nums[i];
            }
            if(max < sum)
            {
                max = sum;
            }
        }
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路二

我们必须承认一个事实，就是子数组肯定是以某个位置结尾的。那么如果我们求出以0 ~ numsSize - 1位置结尾的所有子数组的和，那么这些和中的最大值就是最大子数组之和。那具体是怎么操作的呢？见下图：

为了完成这个操作，我们需要定义几个变量prev和max。prev初始化为nums[0]（以 0 位置结尾的最大子数组和），代表以i-1位置结尾的最大子数组和。而max也初始化为nums[0]，因为现在只知道以 0 位置结尾的最大子数组和。最后利用for循环（从 1 位置开始），看能不能把最大子数组和max推高。

int myMax(int a, int b)
{
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize)
{
    int prev = nums[0];//prev表示以i-1位置结尾的最大子数组和
    int max = nums[0];//max为nums数组的最大子数组和
    for(int i = 1; i < numsSize; i++)
    {
        //当prev > 0时，以i位置结尾的最大子数组和为nums[i] + prev
        //当prev < 0时，以i位置结尾的最大子数组和为num[i]
        prev = nums[i] + (prev > 0 ? prev : 0);
        max = myMax(prev, max);//看prev能否更新max
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路三

定义两个变量cur = 0和max = INT_MIN，利用for循环遍历数组。在for循环中，cur += nums[i]，然后判断cur是否大于max，如果cur > max，那么max = cur。当 cur < 0 时，cur = 0；当 cur >= 0时，cur保持不变。接下来，我就证明一下这个方法。见下图：

//假设答案法
int myMax(int a, int b)
{
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize)
{
    int cur = 0;
    int max = INT_MIN;
    int i = 0;
    for(i = 0; i < numsSize; i++)
    {
        cur += nums[i];
        max = myMax(cur, max);
        cur = cur < 0 ? 0 : cur;
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

👉总结👈

本篇博客主要讲解了LeetCode题最大子数组和，给出了三种思路。其中第一种思路最简答也最为暴力。第二种思路，有点动规划的思想。第三种思路是假设答案法，先假设答案，再写代码来验证。如果大家觉得文章写得不错，大家给个三连支持一下哦！谢谢大家啦！💖💝❣️