蓝桥杯例题六

奋斗是一种态度，也是一种生活方式。无论我们面对什么样的困难和挑战，只要心怀梦想，坚持不懈地努力，就一定能够迈向成功的道路。每一次失败都是一次宝贵的经验，每一次挫折都是一次锻炼的机会。在困难面前，我们不能轻易放弃，而应该勇敢地面对，坚持不懈地追求自己的目标。只要我们有梦想，就有追求的动力；只要我们有坚持，就有成功的可能。让我们激发内在的力量，勇敢地面对挑战，努力奋斗，成就自己的人生。不管前方的路有多坎坷，我们都要坚持向前，不断超越自己，用汗水和努力书写属于自己的辉煌篇章。相信自己，励志奋斗，成功势在必得！

蓝桥杯官网蓝桥杯大赛 — 全国大学生TMT行业赛事

刷题力扣 (LeetCode) 全球极客挚爱的技术成长平台

目录

题目11：整数拆分

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

题目12：买卖股票的最佳时机 II

背景描述：

输入格式：

输出格式：

样例输入：

样例输出：

解答过程：

Python代码实现及详细注释：

总结

---

题目11：整数拆分

背景描述：

给定一个正整数 n，将其拆分为至少两个正整数之和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。

输入格式：

输入一个整数 n (2 <= n <= 58)。

输出格式：

输出一个整数，表示可以获得的最大乘积。

样例输入：

10

样例输出：

36

解答过程：

动态规划 是解决此类问题的有效方法。我们使用一个数组 dp 来存储每个整数 i 的最大乘积值，并通过状态转移方程更新 dp[i]。

步骤：

1. 初始化：
   • 创建一个大小为 n+1 的数组 dp，其中 dp[i] 表示整数 i 拆分后的最大乘积。
   • 初始化 dp[2] = 1，因为 2 只能拆分成 1 + 1，乘积为 1。
2. 状态转移：
   • 对于每一个整数 i，尝试将其拆分成 j 和 i-j，并更新 dp[i] 为 max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]))。
3. 结果：
   • 最终 dp[n] 即为所求的最大乘积。

Python代码实现及详细注释：

def integer_break(n):if n == 2:return 1# 初始化dp数组dp = [0] * (n + 1)dp[2] = 1for i in range(3, n + 1):for j in range(1, i // 2 + 1):# 更新dp[i]为当前最大乘积dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]))return dp[n]# 示例输入
n = 10# 调用函数并打印结果
print(integer_break(n))  # 输出: 36

---

题目12：买卖股票的最佳时机 II

背景描述：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（即多次买入和卖出一支股票）。但是，你不能同时参与多个交易（必须在再次购买前出售掉之前的股票）。

输入格式：

第一行包含一个整数 n (1 <= n <= 10^5)，表示价格数组的长度。 第二行包含 n 个整数，表示每一天的价格。

输出格式：

输出一个整数，表示可以获得的最大利润。

样例输入：

6
7 1 5 3 6 4

样例输出：

7

解答过程：

贪心算法 是解决此类问题的有效方法。我们只需要在价格上涨时进行买卖操作，即可获得最大利润。

步骤：

1. 初始化：
   • 设置变量 max_profit 为0，用于记录总利润。
2. 遍历价格数组：
   • 对于每一天的价格，如果当天的价格高于前一天的价格，则将差值累加到 max_profit 中。
3. 结果：
   • 最终 max_profit 即为所求的最大利润。

Python代码实现及详细注释：

def max_profit(prices):max_profit = 0for i in range(1, len(prices)):# 如果当天的价格高于前一天的价格，则进行买卖操作if prices[i] > prices[i - 1]:max_profit += prices[i] - prices[i - 1]return max_profit# 示例输入
prices = [7, 1, 5, 3, 6, 4]# 调用函数并打印结果
print(max_profit(prices))  # 输出: 7

总结

这两个题目分别涉及了不同的算法思想和技巧：

• 整数拆分 使用了动态规划的方法，适用于处理需要寻找最优子结构的问题。
• 买卖股票的最佳时机 II 使用了贪心算法，这是一种常见的用于优化问题的方法，特别适合用于寻找局部最优解以达到全局最优解的情况。