Dynamic programming: Its particularity allows the process to be divided into several interrelated phases, at each of which decisions need to be made to achieve the best activity of the whole process.

Therefore, the selection of decisions at each stage cannot be arbitrarily determined. It depends on the current situation and affects the future development. When the decision of each stage is determined, a decision sequence is formed, and thus an activity route of the whole process is determined.

In the array can be arbitrary can not be adjacent to the number, how to obtain the maximum value and return.

Example:

[100.4.1.99, -100.1000.33.2.1.5.88]
/ / 1289
Copy the code

Solution: Suppose you divide the array into parts to execute the result

  1. Phase 1: When the array length is only 1, it is optimal. So let’s just take the first number

sum[0] = arr[0]

  1. Second stage: the array length is 2, and compare the second and the first number which is larger, the larger result in the second stage of the result

sum[1] = Math.max(arr[0], arr[1])

The subsequent phases are then executed and the results of each execution are saved into the results of each phase.

Sum [1] i-1 is the result of the execution of the previous number.

Sum [0] i-2 is the result of the first selection and the interval of I =2 is 1.

Then the maximum value is obtained when the execution result is compared with the last execution result:

To compare the sum [0] + current value and the sum [1] is Max (arr [2] + sum (2, 2], the sum (2-1]).

  1. When I is equal to 3, what is 99 plus? With the comparison of 3-1 sum[2], i.e., the previous time, take the maximum value

Here? Sum [1] is 100 Max (100,4)

Max (99 + sum[3-2],sum[3-1])

It is deduced that Max (ARr [I]+sum[i-2],sum[i-1]) is a dynamic programming chain.

So for loops through the integer set and fetches the final result and sum[leng-1]

function getSum(arr) {
      const sum = []  
      sum[0] = arr[0]
      sum[1] = Math.max(arr[0], arr[1])
      for (let i = 2; i < arr.length; i += 1) {
        sum[i] = Math.max(arr[i] + sum[i - 2], sum[i - 1])}return sum[arr.length - 1]}Copy the code