Analysis of a LeetCode dynamic programming problem.

Topic describes

53. The sum of the largest suborder

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.

Example:

Input: [-- 2, 1, 3, 4, 1, 2, 1, 5, 4], output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.Copy the code

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

Dynamic programming

Before analyzing how to solve this problem using dynamic programming, let’s take a quick look at what dynamic programming (DP) is.

The problems suitable for dynamic programming should conform to “three characteristics of one model”.

A model

A model refers to the optimal solution model of multi-stage decision making. This refers to the process of going through multiple stages of decision making, with multiple states for each decision. Then we find a set of decision sequences that can produce the optimal solution.

Three characteristics

  1. Optimal substructure

The latter decision can be deduced from the previous decision. For example, in the classic 0-1 backpack problem, we put items in the backpack (or not) in turn. When it comes to the NTH decision (whether to put the NTH item in the bag or not), the previous NTH decision has already determined multiple decisions (the previous different decision sequences finally give all the attainable weights in the n-1 decision), and will not change because of the NTH decision.

  1. There was no aftereffect

Once the decision is made at one stage in A, when the decision is made at the next stage, you don’t have to worry about how the decision was derived at stage A. We just need to use the resulting decision sequence.

  1. Repeating subproblem

Different decision sequences may produce repeated states after reaching the end of the NTH decision. Suppose, for example, that the items to be placed in the backpack weigh 2, 4, 2, and 3 respectively. When we enter the stage of deciding whether or not to add a third item, we will see that the two decision sequences of putting the first and third item and putting only the second item have the same weight. That’s the state of repetition, which may or may not happen.

Two approaches to dynamic programming

1. State transition table method

Any problem that can be solved by dynamic programming can be solved by violent search of backtracking method. So we can use a simple backtracking algorithm to try to solve it, find a pattern, draw a recursion tree.

When we find duplicate subproblems, one can use backtracking + “memo” method. The memo is that we store the result of f(n) in a hash table (backtracking often uses recursive functions), and when we call f(n) again, we pull out the cached result directly to reduce double-counting. The second is the state table transfer table method.

Typically, state tables are two dimensional. Each row represents a number of states after a decision at each stage. The two-dimensional array is filled in line by line until the end state is satisfied (for example, 0-1 knapsack problem is the maximum weight of the knapsack, or n items have made a decision, which is the NTH decision). At this point, we only need to find the final result from the final stage (backpack problem is to find a maximum weight value from back to front).

2. State transition equation method

The key is to find the state transition equation. From the optimal substructure, write the recursive formula, which is called the state transition equation.

Dynamic programming solution

So let’s start analyzing the problem.

So first we’re going to try to do this with a transition table.

Take [-2,1,-3,4,-1,2,1,-5,4] as an example for analysis. Let’s draw a recursion tree for analysis.

The sum, (I). I represents the phase I decision, which is whether to select the current element as the starting point of the new subarray or the current element as the successor element of the original subarray. The specific logic is shown below:

At each stage we’re going to get the sum of the two successive subarrays after the decision, and we’re going to compare them to the maximum sum of the previous stage, and we’re going to get the maximum value.

The thing to notice here is that when we choose one of the two cases after the decision and the large case, we do the next iteration, and the other case we don’t need to do the next recursion. Because the sum of the smaller arrays, when you add them to the larger arrays, is going to be smaller than the sum of the larger arrays, so you don’t need to recurse.

Js code implementation

var maxSubArray = function(nums) {// Dynamic programminglet len = nums.length;
    let max = nums[0];
    let prevSum = nums[0];

    for (let i = 1; i < len; i++) {
        prevSum = Math.max(nums[i], prevSum + nums[i]);
        max = Math.max(max, prevSum);
    }
    return max;
};
Copy the code

reference

  • The beauty of data structures and algorithms
  • LeetCode antithesis