“This is the 34th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Maximum Subarray and Maximum Subarray

LeetCode portal 53. Maximum subarray sum

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.

A subarray is a contiguous part of an array.

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

A subarray is a contiguous part of an array.

Example:

Input: nums = [-2.1, -3.4, -1.2.1, -5.4]
Output: 6
Explanation: [4, -1.2.1] has the largest sum = 6.

Input: nums = [1]
Output: 1

Input: nums = [5.4, -1.7.8]
Output: 23
Copy the code

Constraints:

• 
  $1 <= nums.length <= 10^5$
• 
  $-10^4 <= nums[i] <= 10^4$

Thinking line

Their thinking

We want to solve for the maximum suborder sum of a set of numbers, and we can think about, what combination is good for the result if we go from front to back? Nums [I] = nums[I] = nums[I] = nums[I] = nums[I] During the whole process, we recorded the size of sum. Finally, when the traversal is completed, we only need to obtain the maximum value of sum.

So let’s say sum is equal to 0, and then we go back and forth, at step I.

• Sum = sum + nums[I]

• Sum = nums[I] = nums[I]

• Compare sum and ANS each time, set the maximum value to ANS, and return the result at the end of the traversal

Based on the above considerations, I wrote the following code:

function maxSubArray(nums: number[]) :number {
    let max = -Infinity;
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum = sum > 0 ? sum + nums[i] : nums[i]
        max = Math.max(max, sum)
    }
    return max;
};
Copy the code

Time complexity

O(n): n is the length of the array. Since we need to traverse the array once, the time complexity is O(n).

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.