How to find the largest suborder sum in leetcode
Editor to share with you how to find the largest sub-order and leetcode, I believe that most people do not know much, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!
Topic link
Https://leetcode-cn.com/problems/maximum-subarray/
Topic description
Given an integer array nums, find a continuous subarray with the largest sum (the subarray contains at least one element) and return its maximum sum.
Example:
Input: [- 2, 1, 1, 4, 4, 1, 2, 1, 2, 1, 5, and 4]
Output: 6
Explanation: the sum of the continuous subarray [4 mai Yu 1 JI 2 Jue 1] is the largest, which is 6.
Advanced:
If you have implemented a solution with a complexity of O (n), try to use a more subtle divide-and-conquer method.
The idea of solving the problem
Tags: dynamic plannin
It is not difficult to solve this problem with the idea of dynamic programming, but it is more difficult to use the divide-and-conquer method proposed later, but because it is not the optimal solution, it will not be listed first.
Dynamic programming is to traverse the array first. The current maximum continuous subsequence sum is sum, and the result is ans.
If sum > 0, sum has a gain effect on the result, and sum retains it and adds the current ergodic number
If sum 0) {
Sum + = num
} else {
Sum = num
}
Ans = Math.max (ans, sum)
}
Return ans
}
}
JavaScript version
/ * *
* @ param {number []} nums
* @ return {number}
, /
Var maxSubArray = function (nums) {
Let ans = nums [0]
Let sum = 0
For (const num of nums) {
If (sum > 0) {
Sum + = num
} else {
Sum = num
}
Ans = Math.max (ans, sum)
}
Return ans
}
Drawing and interpretation
The above is all the contents of the article "how to find the largest suborder and sum in leetcode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!
