题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

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

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

解题思路

采用动态规划算法，依次遍历数组的每个元素，并记录前面i - 1个元素的最大和preSum，若preSum < 0, 则从当前元素重新开始计算；若 preSum > 0，则当前最大和为preSum + nums[i]。

代码

int maxSubArray(int* nums, int numsSize){

    if((nums == NULL) || (numsSize == 0))
        return 0;

    int maxRes = nums[0];
    int preSum = nums[0];

    for (int i = 1; i < numsSize; i++)
    {
        if(preSum < 0)
            preSum = nums[i];
        else
            preSum += nums[i];
        
        if(preSum > maxRes)
            maxRes = preSum;
    }

    return maxRes;
}

测试代码及结果

int main(void)
{
    // 功能测试
    int nums1[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};  // 数组中有正有负
    int res1 = maxSubArray(nums1, sizeof(nums1) / sizeof(int));
    printf("res1 = %d\n", res1);

    int nums2[] = {2, 1, 3, 4, 1, 2, 1, 5, 4};  // 数组中只有正数
    int res2 = maxSubArray(nums2, sizeof(nums2) / sizeof(int));
    printf("res2 = %d\n", res2);

    int nums3[] = {-2, -1, -3, -4, -1, -2, -1, -5, -4};  // 数组中只有负数
    int res3 = maxSubArray(nums3, sizeof(nums3) / sizeof(int));
    printf("res3 = %d\n", res3);

    // 特殊输入测试
    int nums4[] = {};  // 数组为空指针
    int res4 = maxSubArray(nums4, sizeof(nums4) / sizeof(int));
    printf("res4 = %d\n", res4);

    return 0;
}

image

执行结果

时间复杂度：O(n)，空间复杂度：O(1)。

image