1. Question
Give you an array of integersnums, please find a continuous subarray with the largest sum (the subarray contains at least one element) and return its maximum sum. A subarray is a continuous part of an array.
Example 1:enter:nums = [-2,1,-3,4,-1,2,1,-5,4]Output:6Explanation: Continuous subarrays[4,-1,2,1]and the largest, for6。
Example 2:enter:nums = [1]Output:1
Example 3:enter:nums = [5,4,-1,7,8]Output:23
1 <= <= 105-104 <= nums[i] <= 104
Advanced:If you have achieved the complexityO(n)Try to use a more exquisite solutionDividing and treating methodsSolve.
2. Code
【1】Dynamic Programming:AssumptionsnumsThe length of the array isn, subscript from0arriven−1. We usef(i)RepresentativeiThe "maximum sum of continuous subarrays" at the end of the number, then it is obvious that the answer we ask for is:max0≤i≤n−1{f(i)}Therefore, we only need to find out thef(i), then returnfThe maximum value in the array is enough. So how do we askf(i)Woolen cloth? We can considernums[i]Become a part alone or joinf(i−1)The corresponding paragraph depends onnums[i]andf(i−1)+nums[i]We hope to obtain a relatively large size, so we can write such a dynamic programming transfer equation:f(i)=max{f(i−1)+nums[i],nums[i]}It's not difficult to give a time complexityO(n), space complexityO(n)The implementation offArray to savef(i)The value of the , use a loop to find allf(i). Considerf(i)Onlyf(i−1)Related, so we can only use one variablepreTo maintain for the currentf(i)off(i−1)What is the value of the space, so that the complexity of the space is reduced toO(1), this is a bit similar to the idea of "rolling arrays".
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = (pre + x, x);
maxAns = (maxAns, pre);
}
return maxAns;
}
}
Time complexity: O(n),innfornumsThe length of the array. We just need to iterate through the array to get the answer.
Space complexity: O(1). We only need constant space to store several variables.
【2】Divide and conquer:This division and governance method is similar to the "line segment tree solves the longest common ascending sub-sequence problem"pushUpoperate. Maybe the reader has not been exposed to the line segment tree yet, so it doesn’t matter. The content of method 2 assumes that you do not have any basis for the line segment tree. Of course, if readers are interested, it is still very interesting to recommend reading the line segment tree interval merging method to solve the "longest continuous ascending sequence problem" and "maximum sub-segment and problem" that have been asked multiple times.
We define an operationget(a, l, r)Indicates a queryasequence[l,r]The largest sub-segment in the interval, then the final answer we ask isget(nums, 0, () - 1). How to divide and conquer this operation? For an interval[l,r], we takem=⌊l+r2⌋, for the interval[l,m]and[m+1,r]Divide and conquer solutions. When recursively penetrates layer by layer until the interval length is reduced to1When it is recursively "started to rebound". At this time, we consider how to pass[l,m]interval information and[m+1,r]The information of the interval is merged into the interval[l,r]information. The two most critical issues are:
1. What information do we need to maintain in the interval?
2. How do we combine this information?
For an interval[l,r], we can maintain four quantities:
1、lSumexpress[l,r]Withinlis the largest subsegment of the left endpoint and
2、rSumexpress[l,r]Withinris the largest subsegment of the right endpoint and
3、mSumexpress[l,r]The largest sub-segment and
4、iSumexpress[l,r]The interval and
The following abbreviation[l,m]for[l,r]"Left sub-section",[m+1,r]for[l,r]"right sub-section". We consider how to maintain these quantities (how to obtain them through the merge of information in the left and right sub-intervals[l,r]information)? For length1The interval[i,i], the values of all four quantities are asnums[i]equal. For length greater than1The interval:
1. The best maintenance isiSum, interval[l,r]ofiSumIt's equivalent to "left sub-section"iSumAdd "right sub-section"iSum。
2. For[l,r]oflSumThere are two possibilities, either equal to the "left sub-interval"lSum, or equal to the "left sub-section"iSumAdd "right sub-section"lSum, the two are big.
3. For[l,r]ofrSum, Similarly, it is either equal to the "right sub-interval"rSum, or equal to the "right sub-interval"iSumAdd "left sub-section"rSum, the two are big.
4. After calculating the above three quantities, it is easy to calculate.[l,r]ofmSumNow. We can consider[l,r]ofmSumWhether the corresponding interval crossesm——It may not crossm, that is[l,r]ofmSumMaybe it's "left sub-section"mSumand "right sub-section"mSumone of them; it may also crossm, maybe it is the "left sub-section"rSumand "right sub-section"lSumSeek sum. The three are big.
This problem is solved.
class Solution {
public class Status {
public int lSum, rSum, mSum, iSum;
public Status(int lSum, int rSum, int mSum, int iSum) {
= lSum;
= rSum;
= mSum;
= iSum;
}
}
public int maxSubArray(int[] nums) {
return getInfo(nums, 0, - 1).mSum;
}
public Status getInfo(int[] a, int l, int r) {
if (l == r) {
return new Status(a[l], a[l], a[l], a[l]);
}
int m = (l + r) >> 1;
Status lSub = getInfo(a, l, m);
Status rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}
public Status pushUp(Status l, Status r) {
int iSum = + ;
int lSum = (, + );
int rSum = (, + );
int mSum = ((, ), + );
return new Status(lSum, rSum, mSum, iSum);
}
}
Hypothetical sequenceaThe length ofn。
Time complexity:Suppose we regard the recursive process as a preorder traversal of a binary tree, then the gradual upper bound of the depth of this binary tree isO(logn), the total time here is equivalent to traversing all nodes of this binary tree, so the gradual upper bound of the total time isO(∑i=1logn2i−1)=O(n), so the gradual time complexity isO(n)。
Space complexity:Recursively useO(logn)The stack space, so the gradual space complexity isO(logn)。
Off topic:Compared with "Method 2", the time complexity is the same, but because of the use of recursion and the maintenance of four information structures, the running time is slightly longer, and the spatial complexity is not as good as Method 1, and it is difficult to understand. So what is the significance of this method?
This is indeed the case for this question. But if you look closely at "Method 2", it can not only solve the interval[0,n−1], can also be used to solve any sub-interval[l,r]The problem. If we put[0,n−1]All sub-interval information that appears after the division is stored is memorized by heap storage, that is, after a real tree is built, we canO(logn)We can even modify the values in the sequence to do some simple maintenance, and then we can stillO(logn)The answers in any range can be obtained within a time period. In the case of large-scale query, the advantages of this method are reflected. This tree is a magical data structure mentioned above - a line segment tree.
Summarize
This is the end of this article about the largest subarray and Java implementation. For more related largest subarray and Java content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!