Nuggets team number online, help you Offer impromptu! Click on theCheck the details

preface

The first time to participate in the Nuggets punch card activity, among other things, mainly rush to reward. 4.12 Start to rush to achieve the small goal of question 14!! This is problem 13.

Topic describes

Maximum suborder sum

For the title description, I mainly use the screenshot leetcode, so the title is as follows

Thought analysis

Divide and conquer is a good way to solve the problem. The concept of divide and conquer is very simple.

Look at the good ones, still not a good idea to solve the problem. Do it your own stupid way. It is a sum of consecutive arrays, so I can iterate over a set of maximum values starting with itself (starting at subscript 0 and ending with itself), and then find the maximum value of the array.

After writing, I felt the logic was ok. I clicked submit and kept loading. I thought it would time out, but I succeeded at last

It is a waste of memory, so change it to a number, and then compare the total value and record the Max value each time, run as follows:

You can see that the memory consumption has increased a lot, and now the problem is the optimization time, and now the time complexity is O(n ^ 2), so I need to think about it.

AC code

/** * @param {number[]} nums * @return {number} */ // 1 var maxSubArray = function(nums) { if(nums.length===1){ return nums[0] } let maxArr = [] for(let i=0; i<nums.length; i++){ let total=nums[i] let total2 = 0 for(let j = i; j<nums.length; j++){ total2+=nums[j] if(total<total2){ total=total2 } } maxArr.push(total) } return Math.max(... maxArr) }; // 2 var maxSubArray = function(nums) { if(nums.length===1){ return nums[0] } let max = nums[0] for(let i=0; i<nums.length; i++){ let total=nums[i] let total2 = 0 for(let j = i; j<nums.length; j++){ total2+=nums[j] if(total<total2){ total=total2 } } if(total>max){ max=total } } return max };Copy the code

conclusion

Persistence is victory. Problem 13 algorithm complete, persistence is victory!!

Left left left

→ Algorithm series link ←

Write write write

You can order it here! You can order it here! You can order it here!