A: hi! ~ Hello everyone, I am YK bacteria 🐷, a microsystem front-end ✨, love to think, love to summarize, love to record, love to share 🏹, welcome to follow me 😘 ~ [wechat account: Yk2012Yk2012, wechat public account: ykyk2012]
“This is the 29th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”
In fact, I wrote this problem in my official account three years ago: divide and conquer to solve the largest subcolumn and problem — and the fastest and fastest to solve the largest subcolumn and problem — online processing at that time was still using C language, today we use JavaScript to explore this problem again. Our real purpose is through this problem, learn some algorithm ideas, learn some methods and skills to solve problems!
53. Maximum suborder sum
Leetcode-cn.com/problems/ma…
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.
① Preliminary study: peace by violence
We can think of the simplest and most violent way to do this, which is to sum up all the subcolumns, and then compare them one by one, and take the largest subcolumn sum.
/ * * *@param {number[]} nums
* @return {number}* /
var maxSubArray = function (nums) {
let thisSum = -Infinity;
let maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
thisSum = 0; // nums[I] to nums[j
for (let k = i; k <= j; k++) {
thisSum += nums[k];
if (thisSum > maxSum) { // If the subcolumn sum you just got is larger
maxSum = thisSum; // Update the result}}}}return maxSum;
};
Copy the codeThe test was correct
But it was too inefficient to pass all the test cases
There are three cycles, so his time is O(N3)O(N^{3})O(N3).
And if you think about it a little bit, do you really need to sum all of these? Is there a lot of repeated summation, can we optimize it?
② Progress: optimization of summation
Let’s transform the third loop, and the third loop is not really necessary, just add one element to the previous one, and you get a new sum
The improved code
/ * * *@param {number[]} nums
* @return {number}* /
var maxSubArray = function(nums) {
let thisSum = -Infinity;
let maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
thisSum = 0; // nums[I] to nums[j
for (let j = i; j < nums.length; j++) {
thisSum += nums[j];
// For the same I, different j, just add one term on the basis of the j-1 cycle
if (thisSum > maxSum) {// If the sum we just got is larger
maxSum = thisSum; // Update the result}}}return maxSum;
};
Copy the codeAs you can see, the time complexity is only O(N2)O(N^{2})O(N2), and of course, that doesn’t run LeetCode
O(N^{2})O(N ^{2})O(N ^ 2), the immediate response is: how do I reduce it to O(NlogN)O(NlogN)O(NlogN)?
③ Divide and rule
The algorithmic idea that we use is — divide-and-conquer 1) divide it into two or more smaller problems; 2) Solve each small problem separately; 3) The solution to the original problem can be obtained by combining the solutions to the small problems.
In this case, what we did was we split the sequence in half, and then we split the sequence in half. Solve a big problem into a lot of small problems to deal with, and then respectively across their boundaries, the problem together.
Let’s take a concrete example. Let’s give you a sequence
So let’s divide it into pairs (take the left side as an example)
The largest subcolumn sum is 4, and everything else is similar
And then across the middle line
The largest subcolumn sum on the left is 6, and the largest subcolumn sum on the right is similar
And then finally you get the largest subcolumn sum in the middle
The largest subcolumn sum is 11
The encoding is as follows
/ * * *@param {number[]} nums
* @return {number}* /
function maxSubArray(nums) {
let len = nums.length
if(len === 0) {return 0
}
return maxSubArraySum(nums, 0, len - 1)};// Computes the maximum sum of intersecting suborders
function maxCrossingSum(nums, left, mid, right){
let sum = 0
let leftSum = -Infinity
for(let i = mid; i >= left; i--){
sum += nums[i]
if(sum > leftSum){
leftSum = sum
}
}
sum = 0
let rightSum = -Infinity
for(let i = mid + 1; i <= right; i++){
sum += nums[i]
if(sum > rightSum){
rightSum = sum
}
}
return (leftSum + rightSum)
}
// Calculate the maximum suborder and function
function maxSubArraySum(nums, left, right){
if(left === right){
return nums[left]
}
let mid = Math.floor((left + right)/2)
let leftSum = maxSubArraySum(nums, left, mid)
let rightSum = maxSubArraySum(nums, mid+1, right)
let crossSum = maxCrossingSum(nums, left, mid, right)
return max3(leftSum, rightSum, crossSum)
}
// Returns the maximum of three numbers
function max3(num1, num2, num3){
return Math.max(num1, Math.max(num2, num3))
}
Copy the codeI finally got out, but I still can’t do it efficiently
Divide-and-conquer optimization: line tree
So let’s optimize, divide and conquer and we can solve for the longest common ascending subsequence with a line segment tree, so let’s just look at the code
function Status(lSum, rSum, mSum, iSum) {
this.lSum = lSum; // lSum represents the largest sum of subsegments within [l,r] whose left endpoint is L
this.rSum = rSum; // rSum represents the sum of the largest subsegments in [l,r] with r as the right endpoint
this.mSum = mSum; // mSum represents the largest sum of subsegments in [l,r]
this.iSum = iSum; // iSum represents the interval sum of [l,r]
}
function pushUp(lSub, rSub){
// iSum is the sum of left subinterval + right subinterval
const iSum = lSub.iSum + rSub.iSum;
// lSum is the lSum and the left interval of the left subinterval
const lSum = Math.max(lSub.lSum, lSub.iSum + rSub.lSum);
// rSum represents the sum of the largest subsegments in [l,r] with r as the right endpoint
const rSum = Math.max(rSub.rSum, rSub.iSum + lSub.rSum);
// mSum represents the largest sum of subsegments in [l,r]
const mSum = Math.max(Math.max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
// Query the maximum sum of subsegments in a sequence [l,r]
function getInfo(a, l, r){
// Recursive termination condition
if (l === r) {
return new Status(a[l], a[l], a[l], a[l]);
}
// The following is the process of "dividing"
// Get the median value
const m = (l + r) >> 1;
// Divide and conquer: left
const lSub = getInfo(a, l, m);
// Divide and conquer
const rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}
var maxSubArray = function(nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
};
Copy the codeThe time complexity here is O(N)O(N)O(N) space complexity O(logN)O(logN)O(logN) O(logN)
⑤ Online processing
ThisSum maintains a right-summing subsum. If the sum of the preceding and subsumes is not as large as the i-th element, a new summing subsum is maintained starting from I
MaxSum holds the maximum sum of suborders in traversal
/ * * *@param {number[]} nums
* @return {number}* /
var maxSubArray = function(nums) {
// The sum of the current suborder
let thisSum = 0;
// Maximum suborder sum
let maxSum = nums[0];
// Walk through the sequence
for(let i = 0; i < nums.length; i++){
if(thisSum + nums[i] < nums[i]){
thisSum = nums[i];
}else{
thisSum += nums[i];
}
if(thisSum > maxSum){ maxSum = thisSum; }}return maxSum;
};
Copy the codeSimplify your code
/ * * *@param {number[]} nums
* @return {number}* /
var maxSubArray = function(nums) {
let thisSum = 0;
let maxSum = nums[0];
for(let i = 0; i< nums.length; i++){
thisSum = Math.max(thisSum + nums[i], nums[i]);
maxSum = Math.max(maxSum, thisSum);
}
return maxSum;
};
Copy the codeThe time is O(N)O(N)O(N), the space is O(1)O(1)O(1) O(1)
