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

The title

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 1:

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Example 2:

Input: nums = [1] Output: 1Copy the code

Example 3:

Input: nums = [0] Output: 0Copy the code

Example 4:

Input: nums = [-1] Output: -1Copy the code

Their thinking

Firstly, the array is traversed. The current maximum sum of continuous subsequence is sum, and the result is ANS. If sum > 0, it means that sum has gain effect on the result, and sum is retained and added to the current traversal number. If sum <= 0, it means that sum has no gain effect on the result and needs to be discarded, and sum is directly updated to the current traversal number. Compare sum and ANS each time, set the maximum value to ANS, and return the result at the end of the traversal

Code implementation

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        returnans; }}Copy the code

The last

Time complexity: O(n)

Space complexity: O(1)

Previous articles:

  • Binary tree brush summary: binary search tree properties
  • Binary tree summary: binary tree properties
  • Binary tree summary: binary tree modification and construction
  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~