解题步骤 1.确定状态 数组下标不断移动，在移动过程中，最大子数组也不断变化，所以状态为子数组最大值。 2.确定dp数组 在本题中，可定义一维数组dp[x]，其中dp[i]表示以第i个元素结尾最大子数组的值 3.确定选择 针对第i个元素，实际上是有两种选择，一种是与arr[i-1]相连，形成一个最大子数组，一种是自成一派。 4.定义base case dp[0] = arr[0] 5.思考状态转移方程 6.代码示例 import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { ...

一、0-1背包 第一类问题：最大价值 确定状态 容量+剩余物品数量 确定选择 针对一个物品放入背包或者不放入背包两种选择 确定dp含义 dp[i][j]表示针对前i个物品，在容量为j的限制下，所能存放的最大价值 确定base case 当物品数量为0或者背包体积为0时，最大价值为0，即dp[0][x]=0,dp[x][0]=0 确定状态转移方程 dp[i][j]=max{dp[i-1][j],w[i]+dp[i-1][j-v[i]]]} Java实现 public static int max(int n,int V,int[][] vw){ int[][] dp =...

重点是要想到新建一个数组，用来存放以原数组中每个数结尾的最大连续子数组的最大和。 假设当前遍历到index=n,则当以arr[index]为尾的最大连续子数组和等于max(以arr[index-1]为尾的最大连续子数组的和,arr[index]);