53. Maximum subarray maximum subarray sum

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

Give you an array of integers  nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

A subarray is a contiguous part of an array.

Subarray   Is a continuous part of the array .

Example 1: Example 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: Example 2：

Input: nums = [1]
Output: 1

Example 3: Example 3：

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

Constraints: Tips ：

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.

Advanced ： If you have implemented complexity as  O(n)  Solution method , Try something more subtle   Divide and conquer method   solve .

C Language （ Time limit exceeded ）

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 Language ：

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;
}

Execution results ： adopt

Execution time ：96 ms, In all  C  Defeated in submission 65.95% Users of

Memory consumption ：11.9 MB, In all  C  Defeated in submission 94.63% Users of

Pass the test case ：209 / 209

C Language ：

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;
}

Execution results ： adopt

Execution time ：88 ms, In all  C  Defeated in submission 97.43% Users of

Memory consumption ：12.3 MB, In all  C  Defeated in submission 8.30% Users of

Pass the test case ：209 / 209