[Dynamic programming] Maximum sum of consecutive subarrays

Dynamic programming (DP): Each state in dynamic programming must be derived from the previous state, which is different from greed, which has no state derivation, but selects the optimal from the local.

Dynamic programming problem solving steps

1: Determine the dp array, dp[ i ] is the maximum consecutive subsequence sum before subscript i.

2: Determine the state transition equation, dp[ i ] has two directions, dp[ i-1 ]+nums[ i ] is adding the current continuous subsequence sum,

num[ i ] is the sum of subsequences to index i calculated from scratch.

3: Initialize dp array, this topic can see that dp[ i ] depends on dp[ i-1 ], so dp[ 0 ] is the basis of recursive company.

4: Determine the traversal order, this question needs to be traversed from front to back.

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0]; //Initialize dpint max = dp[0]; // output the maximum value as an intermediate variablefor(int i = 1;i