preface

In the first semester of my junior year, I planned to change my career, but I didn’t start to brush up on algorithms and prepare for software competitions until the second semester. In the process of learning, I can obviously feel the gap with others, maybe the problem is less… So today I start the first brush question punch card!

I. Title Description:

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. Difficulty: Easy

Example 1

Input: nums = [-- 2, 1, 3, 4, 1, 2, 1, 5, 4] < br > 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

Tip:

1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5
Copy the code

Ii. Analysis of Ideas:

Now, some of you are probably already confused when you look at a subsequence, what is a subsequence?Copy the code

Here’s a chestnut. Let’s say we have a number listed as -6,-4,3,7,8,10. In this sequence, the contiguous elements are taken to form a new sequence, that is, a subsequence, such as -4, 3, 7,8,10, etc. The subsequence can also be empty, if all the integers in the sequence are negative, its maximum subsequence is 0. So what this problem is saying is, find the maximum sum of these subsequences. The first method I came up with was the exhaustive method, which considered all the cases and traversed them all by using the for loop. However, the time complexity of this method was O(n^3), which was too large and exceeded the time limit, so I abandoned it and adopted another method: dynamic programming method. Our usual way of thinking is to start with the first element of the sequence, then the second, then the third… Dynamic programming is different. It is based on the end point of the sub-sequence. When the sequence value at a certain position is less than the next element, the traversal starts directly from the next element and calculates the maximum traversal value.

  • If the length of the array is 1, return the value of the array. If there is only one array, the maximum sequence value should be 0.
if (! nums.length) { return nums[0]; };Copy the code
  • Sets the final end point and the value of the initial sequence length
let max_ending_here = nums[0];
    let max = nums[0];
Copy the code
  • It starts with the second element, and if the first sequence value is less than the next element value, it starts with the next element and finds the final maximum
 for (let i = 1; i < nums.length; i ++ ) {
   
        max_ending_here = Math.max ( nums[i], max_ending_here + nums[i]);
        max = Math.max ( max, max_ending_here);
    };
Copy the code

Iii. AC Code:

Function maxSubArray2 (nums) {function maxSubArray2 (nums) {if (! nums.length) { return nums[0]; }; let max_ending_here = nums[0]; let max = nums[0]; for (let i = 1; i < nums.length; Max_ending_here = math. Max (nums[I], max_ending_here + nums[I]); max = Math.max ( max, max_ending_here); }; return max; };Copy the code

Iv. Summary:

When I first brush the algorithm, I always start the for loop. But with the in-depth study, you will soon find that the limitations of exhaustive method is very large, violent solution is very memory, so, or more learning algorithms…

This article is participating in the "Nuggets 2021 Spring Recruitment Campaign", click to see the details of the campaignCopy the code