ARTICLE · 1077372
2026网安习题大全(5)
题目41：最大子数组和
问题描述：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路：使用动态规划（Kadane 算法）。维护当前子数组和 cur，若 cur 加上当前元素后变小，则从当前元素重新开始。用 best 记录遍历过程中的最大值。
Python 代码示例：
1 2 3 4 5 6 7 8 def maxSubArray(nums): cur = best = nums[0] for num in nums[1:]: cur = max(num, cur + num) best = max(best, cur) return best
题目42：跳跃游戏
问题描述：给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
解题思路：使用贪心算法。维护一个变量 reach 表示当前能到达的最远位置。遍历数组，如果当前下标超过了 reach，说明无法到达该位置，返回 False；否则更新 reach = max(reach, i + nums[i])。若最终 reach 能覆盖最后一个下标，则返回 True。
Python 代码示例：
1 2 3 4 5 6 7 8 9 def canJump(nums): reach = 0 for i, num in enumerate(nums): if i > reach: return False reach = max(reach, i + num) return True
题目43：不同路径
问题描述：一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
解题思路：使用动态规划。dp[i][j] 表示到达位置 (i, j) 的路径数。状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]。可以将二维数组优化为一维数组，只保留当前行的状态。
Python 代码示例：
1 2 3 4 5 6 7 8 def uniquePaths(m, n): dp = [1] * n for i in range(1, m): for j in range(1, n): dp[j] += dp[j - 1] return dp[-1]
题目44：零钱兑换
问题描述：给定不同面额的硬币 coins 和一个总金额 amount，计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。
解题思路：使用动态规划。dp[i] 表示凑成金额 i 所需的最少硬币数。初始化为 amount + 1（表示不可达），dp[0] = 0。对每个金额，遍历所有硬币，更新 dp[i] = min(dp[i], dp[i - coin] + 1)。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 def coinChange(coins, amount): dp = [amount + 1] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] <= amount else -1
题目45：最长递增子序列
问题描述：给定一个整数数组 nums，找到其中最长严格递增子序列的长度。
解题思路：使用动态规划 + 二分查找（耐心排序）。维护一个数组 tails，其中 tails[i] 表示长度为 i + 1 的递增子序列的最小末尾元素。遍历 nums，用二分查找找到当前元素在 tails 中的插入位置并替换，最终 tails 的长度即为最长递增子序列的长度。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 import bisectdef lengthOfLIS(nums): tails = [] for num in nums: pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) else: tails[pos] = num return len(tails)
题目46：打家劫舍
问题描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，但相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组 nums，计算在不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
解题思路：使用动态规划。维护两个变量：prev 表示偷到前前一个房屋的最大金额，curr 表示偷到当前房屋的最大金额。状态转移为 curr = max(curr, prev + num)，然后更新 prev。
Python 代码示例：
1 2 3 4 5 6 7 def rob(nums): prev = curr = 0 for num in nums: prev, curr = curr, max(curr, prev + num) return curr
题目47：完全平方数
问题描述：给定一个正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
解题思路：使用动态规划。dp[i] 表示组成数字 i 所需的最少完全平方数个数。初始化为 dp[i] = i（最坏情况全部由 1 组成）。对每个数字，遍历所有小于等于其平方根的平方数，更新 dp[i] = min(dp[i], dp[i - j*j] + 1)。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 def numSquares(n): dp = [i for i in range(n + 1)] for i in range(1, n + 1): j = 1 while j * j <= i: dp[i] = min(dp[i], dp[i - j * j] + 1) j += 1 return dp[n]
题目48：单词拆分
问题描述：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判断 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
解题思路：使用动态规划。dp[i] 表示字符串前 i 个字符能否被成功拆分。对于每个位置 i，遍历之前的每个位置 j，如果 dp[j] 为 True 且 s[j:i] 在字典中，则 dp[i] = True。可以用集合存储字典以加速查找。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 def wordBreak(s, wordDict): word_set = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[n]
题目49：乘积最大子数组
问题描述：给定一个整数数组 nums，找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），返回该子数组的乘积。
解题思路：使用动态规划。由于负数的存在，需要同时维护当前最大值 max_cur 和当前最小值 min_cur。遍历数组时，若当前元素为负数，则交换最大值和最小值，然后分别更新 max_cur = max(num, max_cur * num) 和 min_cur = min(num, min_cur * num)。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 def maxProduct(nums): max_cur = min_cur = result = nums[0] for num in nums[1:]: if num < 0: max_cur, min_cur = min_cur, max_cur max_cur = max(num, max_cur * num) min_cur = min(num, min_cur * num) result = max(result, max_cur) return result
题目50：分割等和子集
问题描述：给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
解题思路：转换为 0-1 背包问题。先计算数组总和，若总和为奇数则直接返回 False。目标和为 total // 2。使用动态规划，dp[j] 表示能否从数组中选出若干元素使其和为 j。从后向前遍历避免重复使用元素。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def canPartition(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] return dp[target]