Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Spring Recruit punch card day 21 chapter 29.

Study like the seedlings of spring, see its increase, day has a director; Drop out of school such as a whetstone, see its loss, loss.

There are so many activities in digging gold. This month, I decided to use GO to brush the questions every day, on the one hand, to improve the algorithm level, on the other hand, to settle the learning of GO language.

Let’s GO!

Topic describes

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.

A subarray is a contiguous part of an array.

The sample

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The maximum sum of continuous subarrays [4,-1,2,1] is 6.

Example 2:

Input: nums = [1]

Output: 1.

Example 3:

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

Output: 23

Tip:

1 <= nums.length <=
1 0 5 10^{5}


− 1 0 4 -10^{4} <= nums[i] <=
1 0 4 10^{4}

Subject analysis

This problem is similar to the previous problem of how much water can be held in a bucket, and the problem of how much water can be held in a bucket is best solved by using a dual pointer.

After the test and calculation of this problem, it is found that the idea of dynamic programming is the optimal solution:

Each node is compared to the previous one, i.e. : is the value of the current node larger? Or is the value of the current node plus the previous node greater?

Take the problem apart, keep doing this comparison, and get the maximum value.

Thinking on

  1. Initialize the maximum value Max, because from scratch, the default maximum value is the value of the array with subscript 0.
  2. The number of times the length of the loop is iterated
  3. Make the logical judgment in the problem analysis in the for loop:
  4. If the value of the current node + the value of the previous node > the value of the current node: We update the value of the current node to the value of the previous node + the current node.
  5. In the for loop, if the current node value after the sum is greater than the current maximum value Max, the Max is updated
  6. Keep doing the loop until you finish
  7. Return Max, which is the largest sum of subarrays we need

AC code

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

The results

conclusion

The complexity of the

Time complexity: O(n), where n is the length of the input array.

Space complexity: O(1), because we only need constant space to store variables.

sources

Source: LeetCode

Link: leetcode-cn.com/problems/ma…

Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The last

Thanks for reading and welcome to like, favorites,coin(attention)!!