Title Description

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 .

Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray  [4,-1,2,1] And the biggest , by  6 .

Example 2：

Input ：nums = [1]
Output ：1

Example 3：

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

（ source ： Power button （LeetCode） link ：https://leetcode.cn/problems/maximum-subarray）

      The difficulty of this problem lies in , It is not simply a problem of finding the maximum sum , But for Successive The largest sum of subarrays . The first idea is to assume that the maximum and initial are nums[0], From the second number num[1] Start traversing the entire array , If num[0]>0, Update num[1] The value of is num[1]+num[0], If num[0]<0, Do not update the array , Enter the next cycle , If num[1]>0, Update num[2] The value of is num[2]+num[1]……maxSum Is the present maxSum and num[i] The maximum of both .

The code is as follows ：

class Solution 
{
public:
    int maxSubArray(vector<int>& nums)
     {
        int maxSum = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i-1] > 0)
            {
                nums[i] += nums[i-1];
            }
            maxSum = max(maxSum, nums[i]);
        }
        return maxSum;
    }
};

The time complexity is O(n).

There is another solution to this problem （ Violence solution ）, It's a double-layer cycle, each update max Value , This solution is easy to think of , But it may exceed the time limit ：

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        // Similar to the problem of finding the maximum and minimum value , The initial value must be defined as the theoretical minimum and maximum value 
        int max = 0;
        int numsSize = int(nums.size());
        for (int i = 0; i < numsSize; i++)
        {
            int sum = 0;
            for (int j = i; j < numsSize; j++)
            {
                sum += nums[j];
                if (sum > max)
                {
                    max = sum;
                }
            }
        }
        return max;
    }
};

The starting point of outer cycle control is i, The inner loop starts from i Start continuous summation , Find continuous and sum The maximum of , The double-layer loop result will find the maximum value of the sum of the continuous sub arrays of the entire array max.

The time complexity is O(n^2).