第二天 线性动态规划
2.1 53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [0] 输出：0
示例 4：
输入：nums = [-1] 输出：-1
示例 5：
输入：nums = [-100000] 输出：-100000
提示：
class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; dp[0] = nums[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); } int maxn = nums[0]; for (int i = 0; i < n; i++) { maxn = Math.max(dp[i],maxn); } return maxn; } }
空间复杂度进行优化
class Solution { public int maxSubArray(int[] nums) { int pre = 0, res = nums[0]; int n = nums.length; for (int i = 0; i < n; i++) { pre = Math.max(pre + nums[i],nums[i]); res = Math.max(pre,res); } return res; } }
2.2 198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
由此，可以写出该题目代码，
Java代码如下：
class Solution { public int rob(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; if (n == 1) { return dp[0]; } dp[1] = Math.max(nums[0],nums[1]); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]); } return dp[n - 1]; } }
空间复杂度优化
class Solution { public int rob(int[] nums) { int pre = 0; int cur = 0; for (int i = 0; i < nums.length; i++) { int tmp = Math.max(pre + nums[i],cur); pre = cur; cur = tmp; } return cur; } }
2.3 213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [0] 输出：0
提示：
Java代码如下：
class Solution { public int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } return Math.max(myrob(Arrays.copyOfRange(nums,0,nums.length-1)),myrob(Arrays.copyOfRange(nums,1,nums.length))); } public int myrob(int[] nums) { int pre = 0; int cur = 0; for (int i = 0; i < nums.length; i++) { int tmp = Math.max(cur,pre + nums[i]); pre = cur; cur = tmp; } return cur; } }
2.4 740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4] 输出：9 解释： 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。 总共获得 9 个点数。
Java代码如下：
class Solution { public int deleteAndEarn(int[] nums) { int maxn = nums[0]; int n = nums.length; for (int i = 0; i < n; i++) { maxn = Math.max(maxn,nums[i]); } int[] dp = new int[maxn + 1]; for (int x : nums) { dp[x] += x; } return rob(dp); } public int rob(int[] nums) { int n = nums.length; int pre = 0, cur = 0; int sum = 0; for (int i = 0;i < n; i++) { sum = Math.max(pre + nums[i],cur); pre = cur; cur = sum; } return cur; } }
喜欢的可以关注微信公众号『进阶的算法小白』，每天更新一点算法知识，一起学习。
