The title
Title link: leetcode-cn.com/leetbook/re…
Answer key
The difficulty of dynamic programming lies in dividing suitable sub-problems and determining state transition equations. A good state transition equation makes programming easier.
In the analysis process of this paper, it reflects the difficult process of finding a state transition equation which is easy to program.
1. Routine analysis of dynamic programming
Why use dynamic programming, which reduces computation when the solution of the current problem can be found from the solution of the recorded subproblem; The following is the analysis process of this problem using dynamic programming;
1.1. Delimit the molecular problem and determine the boundary of subproblems
For the integer array nums of length K, let the sum of the continuous subarray with the largest sum be f(k);
We need an array result to record the subsequence with the largest sum;
-
When length is 1, the sum of the continuous array with the largest sum is f(1) = nums[0];
-
When the length is 2, the sum of the continuous array with the largest sum is f(2) = Max (f(1), nums[1], f(1) + nums[1]);
-
When the length is k
If result ends in nums[k-2],
- If nums[k-1] is greater than 0, f(k) = F (k-1) + NUMs [k-1];
- Nums [k – 1) is less than zero, f (k) = Max (f (k – 1), nums] [k – 1);
If result does not end in nums[k-2],
- If nums[k-1] is greater than 0, then f(k) = Max (f(k-1), sum of the substring ending with nums[k-1] and the largest substring (let it be g(k-1));
- If nums[k-1] is less than 0, f(k) = Max (f(k-1), nums[k-1]);
1.2. Define the optimization function (state transition equation) and list the recursive equation
Among them:
- F (k) : nums the maximum sum of subsequences;
- Nums is an array of integers to be evaluated;
- Nums [k-1] is the KTH integer;
- Result: The sequence of subsequences with the largest subsequence and
- G (k) : the sum of the sequences ending in nums[k-1] with the maximum sequence sum;
Conclusion: From the above state transition equation, we know that the size of F (k) depends on the size of F (k-1), which meets the optimization principle, so dynamic programming can be used.
Further analysis:
by
- F (k) : the sum of the largest subsequence of the sequence nums
- G (k) : sum of subsequences ending in nums[k-1] with the maximum sequence sum;
According to the definition and constraints of G (k), the recursive equation can be written as:
F (k-1) = Max (g(1)… G of k minus 1, so
From this recursive equation, we know that we can solve for g(1)… G (nums.length) and result (f(nums.length));
Description of the algorithm for solving g(x) (note that k starts at 1 and nums starts at 0)
- When k = 1, g(1) = nums[0];
- When k = 2, g(1) > 0, g(2) = g(1) + NUMs [1]; When g(1) <= 0, g(2) = nums[1];
- When k = I, g(i-1) > 0, g(I) = g(i-1) + NUMs [i-1]; When g(i-1) <= 0, g(I) = nums[i-1];
In the process of solving g(x), the corresponding sub-sequence result can be obtained;
1.3 code implementation
The code executes, but faces a large amount of data because the cache of g and result is too large, exceeding leetCode’s heap size limit; The utility code uses the following optimization algorithm;
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { if(nums.length === 1) { return nums[0]; } result function getG(nums) {const g = []; const len = nums.length; for(let i = 1; i <= len; i++) { // console.log(g,'----') if(1 === i) { g.push({ sum:nums[0], result:[nums[0]] }) }else { const preSum = g[i-2].sum; if( preSum > 0) { g.push({ sum:preSum + nums[i-1], result:[...g[i-2].result,nums[i-1]] }) }else { g.push({ sum:nums[i-1], result:[nums[i-1]] }) } } } return g; } const len = const len; const len = const len; const len = const len; let preMaxSum = g[0].sum; g.slice(0,len-2).forEach(item => { if(preMaxSum < item.sum) { preMaxSum = item.sum; } }) if(nums[len-1] < 0 ) { return Math.max(preMaxSum,g[len-2].sum,nums[len-1]); }else { if(g[len-2].result[g[len-2].result.length] === nums[len-2]) { return g[len-1].sum; }else { return Math.max(preMaxSum,g[len-1].sum); } } } const g = getG(nums); Result} return ms(nums,g); // nums[k]= nums[k-1]; };Copy the code
2. Improved thinking of dynamic programming analysis
2.1, analysis,
The difficulty of dynamic programming is how to delimit molecules and determine state transition equations.
If f(k) = Max (g(1)… if f(k) = Max (g(1)… G (k));
So we have the recursive equation:
Among them:
- K = nums. Length; (NUMs is an array of integers to be evaluated)
The recursive equation shows that it satisfies the optimization principle.
2.2 code implementation
Use an auxiliary array to store g(k), 1<= k <= nums.length;
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
const g = []; // 存储 g(k) , 1<= k <= nums.length ;
g.push(nums[0])
const len = nums.length;
for(let i = 1;i < len;i++) {
const preSum = g[i-1];
if( preSum > 0) {
g.push(preSum + nums[i])
}else {
g.push(nums[i])
}
}
const gLen = g.length;
let MaxSum = g[0];
// 在 g[0] ... g[nums.length - 1] 中找最大值
for(let i = 1;i < gLen;i++) {
if(sum < g[i]) {
sum = g[i];
}
}
return MaxSum;
};
Copy the code2.3. Code optimization
Because the size of f(k) is only determined by f(k-1) and g(k), we can calculate g(k) by setting f(k-1) = Max (g(1)… ,g(k-1)), so there is no need to use an array to hold g(1)… G (k-1), just use one variable to hold f(k-1);
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { const len = nums.length; let g = nums[0]; let maxSum = g; For (let I = 1; i<len; i++) { if(g>0) { g += nums[i]; }else { g = nums[i]; If (g > maxSum) {maxSum = g; } } return maxSum; };Copy the code
3. Divide and conquer
According to LeetCode’s official answer, divide-and-conquer is also possible, but since I haven’t thought much about it, here’s the link to the official answer:
Leetcode-cn.com/problems/ma…
It involves the concept of line segment trees;
If you have a better way of thinking and reconciliation, welcome to discuss ah ~
Juejin. Cn/post / 700669…