“This is the 16th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] output: 6 explanation: the maximum sum of consecutive subarrays [4,-1,2,1] is 6.Copy the code

Violent solution

The easiest way to solve the problem is to perform a traversal calculation for the entire set of subarrays. The time complexity is O(n^2) :

func maxSubArray(nums []int) int {
   m := nums[0]
   for i := 0; i < len(nums); i++ {
      for j := i; j < len(nums); j++ {
         s := 0
         for t := i; t <= j; t++ {
            s += nums[t]
         }
         if s > m {
            m = s
         }
      }
   }
   return m
}
Copy the code

Of course, there are no unexpected timeouts:

Greedy algorithm

Through observation, it is not difficult to find: when a series of subsequences are extended backward, if the sum of the sequence is already less than 0, then it is better to abandon the substring and rebuild the continuous substring directly from the next element.

For a simple example, if you build a continuous subsequence starting at -2, and the following element is 1, then if you want to add 1 to that subsequence, you get -2, and the sum of 1 is -1. This certainly doesn’t make sense, because we just drop -2 and start again from 1 to build subsequence 1, and the sum is 1 greater than the subsequence above.

Therefore, we can use this property to find the local optimal solution of the subsequence with the subsequence sum being negative as the boundary condition.

At the same time, when the local optimal solution is updated, it can be compared with the global optimal solution. If the local optimal solution is larger than the global optimal solution, it will be updated.

It only takes one walk to get the result, order n time.

The code implementation is as follows:

func maxSubArray(nums []int) int {
   m := nums[0]
   tmp := 0
   for i := 0; i < len(nums); i++ {
      tmp += nums[i]
      if tmp > m {
         m = tmp
      }
      if tmp < 0 {
         tmp = 0}}return m
}
Copy the code

Submit the results