✨今日算法三题
文章目录
1.连续子数组的最大和
题目描述
思路详解
本题的思路较为简单，本题只询问最大子数组的值，并没有说具体求出是哪个子数组，那么我们就可以动态规划来解题。
我们遍历数组进行累加，判断加上后边的这个数是否比之前的子数组大，两者取较大的，然年再比较之前保存的最大结果与当前所得子数组值的大小，取最大值就可以了。
代码与结果
class Solution { public int maxSubArray(int[] nums) { int pre = 0, maxAns = nums[0]; for (int x : nums) { pre = Math.max(pre + x, x); maxAns = Math.max(maxAns, pre); } return maxAns; } }
2.最长递增子序列
题目描述
思路详解
这里的思路，我们维护一个与数组nums等长的数组dp，用来保存与之对应的最大增序列的结果，我们来两层循环，第一层我们遍历数组 i ，同时把dp对应的也赋值为1，进入第二层循 环 j ，本层循环从nums[0]开始到nums[i]的前一个为止。我们进行比较第二层循环的值是否小于nums[i]，如果小的话就把dp[j]的值加1，与dp[i]进行比较，取大值。同时我们保持结果一直是最大就好。
注意，这里可能会有小伙伴有问题，其实呢，我们每次循环都能找出当前以 i 为结尾的增长子序列的最大值并且保存到dp[i]中，那么当二层循环的时候，如果nums[j] < nums[i] 那么不就是以 i 为结尾的增长子序列又长了 1 嘛，因为 i 在 j 的后面，j 本身就是那么长，nums[i] > nums[j] ,那么自然 以 i 为结尾子序列最大长度 就是 dp[j] + 1 了嘛，（记得是（dp[i] , dp[i] + 1）取最大值哦
代码与结果
class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int maxans = 1; for (int i = 1; i < nums.length; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxans = Math.max(maxans, dp[i]); } return maxans; } }
3.统计放置房子的方式数
题目描述
思路详解
单独考虑一侧的房子，定义f[i] 表示前 i 个地块的放置方案数，其中第 i 个地块可以放房子，也可以不放房子。
考虑第 i 个地块：
若不放房子，那么第i−1 个地块可放可不放，则有 f[i] = f[i-1]；
若放房子，那么第 i−1 个地块无法放房子，第i−2 个地块可放可不放，则有 f[i]=f[i−2]。
因此
f[i]=f[i−1]+f[i−2]
边界为
f[0]=1，空也是一种方案；
f[1]=2，放与不放两种方案。
由于两侧的房屋互相独立，根据乘法原理，答案为f[n] ** 2。
代码与结果
class Solution { static final int MOD = (int) 1e9 + 7, MX = (int) 1e4 + 1; static final int[] f = new int[MX]; static { f[0] = 1; f[1] = 2; for (var i = 2; i < MX; ++i) f[i] = (f[i - 1] + f[i - 2]) % MOD; } public int countHousePlacements(int n) { return (int) ((long) f[n] * f[n] % MOD); } }
✨总结
今天练习了动态规划，动态规划一开始就是用f[i]来表示以i为结尾的满足条件的结果数，之后根据条件修改结果。想熟练运用的话，还是要多多练习哦！！！
