53. Maximum Subarray最大子数组和

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

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

A subarray is a contiguous part of an array.

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

Example 1:示例 1：

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:示例 2：

Input: nums = [1]
Output: 1

Example 3:示例 3：

Input: nums = [5,4,-1,7,8]
Output: 23
 

Constraints:提示：

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

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

C语言（超出时间限制）

int maxSubArray(int* nums, int numsSize){
    int max=-10000,temp;
    for(int i=0;i<numsSize;i++)
    {
        temp=nums[i];
        if(max<nums[i])
        {
            max=nums[i];
        }
        for(int j=i+1;j<numsSize;j++)
        {
            temp+=nums[j];
            if(max<temp)
            {
                max=temp;
            }
        }

    }
    return max;
}

C语言：

int maxSubArray(int* nums, int numsSize){
    int cur=nums[0];
    int max=nums[0];
    for(int i=1;i<numsSize;i++)
    {
        if(cur+nums[i]>nums[i])
        {
            cur+=nums[i];
        }
        else
        {
            cur=nums[i];
        }
        if(max<cur)
        {
            max=cur;
        }
    }
    return max;
}

执行结果：通过

执行用时：96 ms, 在所有 C 提交中击败了65.95%的用户

内存消耗：11.9 MB, 在所有 C 提交中击败了94.63%的用户

通过测试用例：209 / 209

C语言：

int maxSubArray(int* nums, int numsSize){
    int cur=0;
    int max=INT_MIN;
    for(int i=0;i<numsSize;i++)
    {
        if(cur<=0)
            cur=nums[i];
        else
            cur+=nums[i];
        if(cur>max)
            max=cur;
    }
    return max;
}

执行结果：通过

执行用时：88 ms, 在所有 C 提交中击败了97.43%的用户

内存消耗：12.3 MB, 在所有 C 提交中击败了8.30%的用户

通过测试用例：209 / 209