After reading this article , You can go and get the following questions ：
53. The largest subsequence and
-----------
The problem of the largest subarray is the same as the one mentioned above Classic dynamic planning ： The longest increasing subsequence It's very similar , It represents a special dynamic programming problem ：
Thought analysis
In fact, the first time I saw this problem , The first thing that came to my mind Sliding window algorithm , Because we said before , Sliding window algorithm is to deal with substring / Subarray problem , This is the subarray problem ？
however , A little analysis reveals that , This problem can't be solved by sliding window algorithm , Because the numbers in the array can be negative .
Sliding window algorithm is nothing more than a double pointer window scanning the entire array / Substring , But the point is , You have to know exactly when to move the right pointer to enlarge the window , When to move the left pointer to decrease the window .
And for this subject , Do you think , When the window expands, you may encounter negative numbers , The values in the window may increase or decrease , In this case, I don't know when to shrink the left window , It's impossible to find out 「 Maximum subarray and 」.
Solving this problem requires dynamic planning skills , however dp The definition of array is special . According to our conventional dynamic planning idea , It is generally defined as dp Array ：
nums[0..i] Medium 「 The largest subarray and 」 by dp[i].
If so defined , Whole nums Array of 「 Maximum subarray and 」 Namely dp[n-1]. How to find the state transition equation ？ According to mathematical induction , Suppose we know dp[i-1], How to deduce dp[i] Well ？
Here's the picture , According to what we said just now dp Definition of array ,dp[i] = 5 , It's equal to nums[0..i] The largest subarray in and ：
So in the case above , Using mathematical induction , You can use dp[i] Introduction dp[i+1] Do you ？
Not really , Because subarrays must be continuous , According to our current dp To define an array , There's no guarantee nums[0..i] The largest subarray in and nums[i+1] It's adjacent , There's no way to get from dp[i] Deduce dp[i+1].
So we define it this way dp The array is not correct , We can't get a proper state transition equation . For this kind of subarray problem , We're going to redefine dp The meaning of array ：
With nums[i] For the end of 「 Maximum subarray and 」 by dp[i].
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
Under this definition , Want the whole thing nums Array of 「 Maximum subarray and 」, Cannot return directly dp[n-1], And you need to traverse the whole thing dp Array ：
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
Still using mathematical induction to find state transition relations ： Suppose we have worked out dp[i-1], How to deduce dp[i] Well ？
It can be done ,dp[i] There are two kinds of 「 choice 」, Or join to the previous adjacent subarray , Form a subarray of and larger ; Or not linked to the previous subarray , A school of its own , Self as a subarray .
How to choose ？ Since it is required that 「 Maximum subarray and 」, Of course, choose the bigger one ：
// Or it's a school of its own , Or merge with the previous subarray
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
Sum up , We've written the state transition equation , You can write the solution directly ：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
// base case
// There is no subarray before the first element
dp[0] = nums[0];
// State transition equation
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// obtain nums The largest subarray of
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
The time complexity of the above solution is O(N), The complexity of space is also O(N), It's better than brute force , however be aware dp[i] Just and dp[i-1] The state of , So we can do 「 State compression 」, Reduce space complexity ：
int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// base case
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
for (int i = 1; i < n; i++) {
// dp[i] = max(nums[i], nums[i] + dp[i-1])
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// By the way, calculate the largest result
res = Math.max(res, dp_1);
}
return res;
}
The final summary
Although the state transition equation derived from dynamic programming is more metaphysical , But most of them have some rules to follow .
Today this 「 Maximum subarray and 」 Just like 「 The longest increasing subsequence 」 Very similar ,dp The definition of an array is 「 With nums[i] Is the largest subarray at the end and / The longest increasing subsequence is dp[i]」. Because only in this way can we define dp[i+1] and dp[i] Build a connection , Using mathematical induction to write the state transition equation .
＿＿＿＿＿＿＿＿＿＿＿＿＿
my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！
