【计算机算法与设计（10）】习题：苹果买卖问题——分治法的经典应用

📖 问题描述：一次买卖，最大化利润

想象你开着一辆车，从城市A到城市B，沿途经过n个苹果市场（编号1到n）。在每个市场i，你都知道：

• 买入价B[i]：在这个市场买苹果的价格
• 卖出价S[i]：在这个市场卖苹果的价格

约束条件：

• 车只能往前开，不能往回开
• 只能做一次买卖：在一个市场买入，在之后的市场卖出（j ≥ i j \geq ij≥i）

目标：找到最优的买入市场i和卖出市场j，使得利润S [ j ] − B [ i ] S[j] - B[i]S[j]−B[i]最大（如果无法盈利，则最小化亏损）。

🧠 为什么不能用简单方法？

❌ 错误思路1：贪心法（每次都选最便宜的买，最贵的卖）

问题：最便宜的买入点可能在最贵的卖出点之后，违反了"不能往回开"的约束。

❌ 错误思路2：转化为最大子数组问题

常见错误：有些同学会联想到股票增值问题，试图将问题转化为最大连续子数组问题。

为什么不行：

• 股票问题中，同一天的买入价和卖出价相同，可以转化为价格差数组
• 但本题中，每个市场的买入价和卖出价不同，不能简单转化

例如：市场4的买入价是2元，卖出价是1元，如果在这里买卖会亏损1元，但我们可以在这里买入，到其他市场卖出。

✅ 正确思路：分治法

分治法的核心思想：将大问题分解为小问题，解决小问题，再合并结果。

分治法的三个步骤

1️⃣底（Base Case）：最简单的情况

如果只有一个市场，那么：

• 只能在这个市场买入并卖出
• 利润 =S [ i ] − B [ i ] S[i] - B[i]S[i]−B[i]

2️⃣分（Divide）：将问题一分为二

将区间[ L , R ] [L, R][L,R]分成两个子区间：

• 左半部分：[ L , Mid ] [L, \text{Mid}][L,Mid]
• 右半部分：[ Mid + 1 , R ] [\text{Mid}+1, R][Mid+1,R]

其中Mid = ⌊ ( L + R ) / 2 ⌋ \text{Mid} = \lfloor (L+R)/2 \rfloorMid=⌊(L+R)/2⌋

⌊ ⌋ \lfloor \rfloor⌊⌋:指的是地板函数：取下标。比如： 当L=0，R=5时：(0+5)/2=2.5，⌊2.5⌋=2

3️⃣合（Combine）：合并子问题的解

最优解可能出现在三种情况中：

1. 完全在左半部分：在左子区间内买入和卖出
2. 完全在右半部分：在右子区间内买入和卖出
3. 跨越中点：在左半部分买入，在右半部分卖出

关键点：对于跨越中点的情况，最优策略是：

• 在左半部分选择最低的买入价B [ left ] B[\text{left}]B[left]
• 在右半部分选择最高的卖出价S [ right ] S[\text{right}]S[right]
• 利润 =S [ right ] − B [ left ] S[\text{right}] - B[\text{left}]S[right]−B[left]

最终答案：从这三种情况中选择利润最大的。

💻 算法伪代码

算法：D&C-Max-Apple-Profit(B[], S[], L, R)输入：买入价数组B[]，卖出价数组S[]，区间[L, R]输出：最大利润M，买入市场i，卖出市场j1.ifL==Rthen// 底：只有一个市场2. M=S[L]- B[L]3. i=L, j=L4.return(M, i, j)5. endif6.else// 分：将问题分解7. Mid=⌊(L+R)/2⌋8.(ML, IL, JL)=D&C-Max-Apple-Profit(B[], S[], L, Mid)// 左子问题9.(MR, IR, JR)=D&C-Max-Apple-Profit(B[], S[], Mid+1, R)// 右子问题10.11. // 合：合并子问题的解12. // 情况3：跨越中点的情况13. B[left]=min{B[u]|L ≤ u ≤ Mid}// 左半部分最低买入价14. S[right]=max{S[u]|Mid+1 ≤ u ≤ R}// 右半部分最高卖出价15. Mc=S[right]- B[left]// 跨越中点的利润16.17. // 从三种情况中选择最优18.ifMc>max(ML, MR)then19. M=Mc, i=left, j=right20.elseifML>MRthen21. M=ML, i=IL, j=JL22.else23. M=MR, i=IR, j=JR24. endif25.26.return(M, i, j)27. endelse

🔍 算法执行过程示例

让我们用示例数据演示算法执行过程：

递归树

[1,6] / \ [1,3] [4,6] / \ / \ [1,2] [3,3] [4,5] [6,6] / \ / \ [1,1] [2,2] [4,4] [5,5]

自底向上合并过程

第1层（叶子节点）：(底)

• [1,1]:M = 3 − 5 = − 2 M = 3-5 = -2M=3−5=−2
• [2,2]:M = 3 − 4 = − 1 M = 3-4 = -1M=3−4=−1
• [3,3]:M = 7 − 8 = − 1 M = 7-8 = -1M=7−8=−1
• [4,4]:M = 1 − 2 = − 1 M = 1-2 = -1M=1−2=−1
• [5,5]:M = 6 − 7 = − 1 M = 6-7 = -1M=6−7=−1
• [6,6]:M = 7 − 9 = − 2 M = 7-9 = -2M=7−9=−2

第2层：

• [1,2]:

  • 左子问题（1,1）:M = − 2 M=-2M=−2
  • 右子问题(2,2):M = − 1 M=-1M=−1
  • 跨越中点:min ⁡ ( B [ 1 ] , B [ 2 ] ) = 4 \min(B[1],B[2])=4min(B[1],B[2])=4,max ⁡ ( S [ 2 ] ) = 3 \max(S[2])=3max(S[2])=3,M c = 3 − 4 = − 1 M_c=3-4=-1Mc​=3−4=−1
  • 最优:M = − 1 M=-1M=−1(右子问题或跨越中点)

• [4,5]:

  • 左子问题:M = − 1 M=-1M=−1
  • 右子问题:M = − 1 M=-1M=−1
  • 跨越中点:min ⁡ ( B [ 4 ] ) = 2 \min(B[4])=2min(B[4])=2,max ⁡ ( S [ 5 ] ) = 6 \max(S[5])=6max(S[5])=6,M c = 6 − 2 = 4 M_c=6-2=4Mc​=6−2=4
  • 最优:M = 4 M=4M=4(跨越中点)

第3层：

• [1,3]:

  • 左子问题[1,2]:M = − 1 M=-1M=−1
  • 右子问题[3,3]:M = − 1 M=-1M=−1
  • 跨越中点:min ⁡ ( B [ 1..2 ] ) = 4 \min(B[1..2])=4min(B[1..2])=4,max ⁡ ( S [ 3 ] ) = 7 \max(S[3])=7max(S[3])=7,M c = 7 − 4 = 3 M_c=7-4=3Mc​=7−4=3
  • 最优:M = 3 M=3M=3(跨越中点)

• [4,6]:

  • 左子问题[4,5]:M = 4 M=4M=4
  • 右子问题[6,6]:M = − 2 M=-2M=−2
  • 跨越中点:min ⁡ ( B [ 4..5 ] ) = 2 \min(B[4..5])=2min(B[4..5])=2,max ⁡ ( S [ 6 ] ) = 7 \max(S[6])=7max(S[6])=7,M c = 7 − 2 = 5 M_c=7-2=5Mc​=7−2=5
  • 最优:M = 5 M=5M=5(跨越中点)

第4层（根节点）：

• [1,6]:
  • 左子问题[1,3]:M = 3 M=3M=3
  • 右子问题[4,6]:M = 5 M=5M=5
  • 跨越中点:min ⁡ ( B [ 1..3 ] ) = 4 \min(B[1..3])=4min(B[1..3])=4,max ⁡ ( S [ 4..6 ] ) = 7 \max(S[4..6])=7max(S[4..6])=7,M c = 7 − 4 = 3 M_c=7-4=3Mc​=7−4=3
  • 最优:M = 5 M=5M=5(右子问题)，买入市场4，卖出市场6

📊 算法复杂度分析

时间复杂度

递推关系：T ( n ) = 2 T ( n / 2 ) + O ( n ) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)

求解过程：

• 每次递归将问题分成两个子问题，每个子问题规模为n / 2 n/2n/2
• 合并步骤需要O ( n ) O(n)O(n)时间（找最小值和最大值）
• 根据主方法，时间复杂度为O ( n log ⁡ n ) O(n \log n)O(nlogn)

⚠️ 常见错误与注意事项

错误2：复杂度分析错误

错误递推式：
T ( n ) = 2 T ( n / 2 ) + O ( 1 ) ❌ 错误！ T(n) = 2T(n/2) + O(1) \quad \text{❌ 错误！}T(n)=2T(n/2)+O(1)❌错误！

错误原因：合并步骤需要处理跨越中点的情况，必须重新扫描整个子区间：

1. 在左半部分[ L , Mid ] [L, \text{Mid}][L,Mid]找最低买入价：

   • 需要遍历左半部分的所有元素：B [ left ] = min ⁡ { B [ u ] ∣ L ≤ u ≤ Mid } B[\text{left}] = \min\{B[u] \mid L \leq u \leq \text{Mid}\}B[left]=min{B[u]∣L≤u≤Mid}
   • 左半部分规模：Mid − L + 1 ≈ n / 2 \text{Mid} - L + 1 \approx n/2Mid−L+1≈n/2
   • 时间复杂度：O ( n / 2 ) = O ( n ) O(n/2) = O(n)O(n/2)=O(n)

2. 在右半部分[ Mid + 1 , R ] [\text{Mid}+1, R][Mid+1,R]找最高卖出价：

   • 需要遍历右半部分的所有元素：S [ right ] = max ⁡ { S [ u ] ∣ Mid + 1 ≤ u ≤ R } S[\text{right}] = \max\{S[u] \mid \text{Mid}+1 \leq u \leq R\}S[right]=max{S[u]∣Mid+1≤u≤R}
   • 右半部分规模：R − ( Mid + 1 ) + 1 ≈ n / 2 R - (\text{Mid}+1) + 1 \approx n/2R−(Mid+1)+1≈n/2
   • 时间复杂度：O ( n / 2 ) = O ( n ) O(n/2) = O(n)O(n/2)=O(n)

3. 总时间：O ( n / 2 ) + O ( n / 2 ) = O ( n ) O(n/2) + O(n/2) = O(n)O(n/2)+O(n/2)=O(n)

为什么不能是O ( 1 ) O(1)O(1)？

• 需要扫描整个子区间才能确定最小值/最大值
• 不能直接使用左右子问题的解，因为跨越中点时的最优选择可能不是子问题的最优解
• 例如：左子问题可能在市场2买入（4元），但跨越中点时市场4的买入价（2元）更低，应该选择市场4

正确递推式：
T ( n ) = 2 T ( n / 2 ) + O ( n ) T(n) = 2T(n/2) + O(n)T(n)=2T(n/2)+O(n)

复杂度求解（使用主方法）：

• a = 2 a = 2a=2,b = 2 b = 2b=2,f ( n ) = O ( n ) f(n) = O(n)f(n)=O(n)
• log ⁡ b ( a ) = log ⁡ 2 ( 2 ) = 1 \log_b(a) = \log_2(2) = 1logb​(a)=log2​(2)=1
• f ( n ) = O ( n ) = O ( n 1 ) = O ( n log ⁡ b ( a ) ) f(n) = O(n) = O(n^1) = O(n^{\log_b(a)})f(n)=O(n)=O(n1)=O(nlogb​(a))
• 情况2：T ( n ) = O ( n log ⁡ n ) T(n) = O(n \log n)T(n)=O(nlogn)

🎯 核心要点总结

1. 问题本质：在约束条件下（j ≥ i j \geq ij≥i）找到最优的买卖组合

2. 分治法三步骤：

   • 底：只有一个市场时，利润 =S [ i ] − B [ i ] S[i] - B[i]S[i]−B[i]
   • 分：将区间分成左右两部分
   • 合：从三种情况中选择最优（左、右、跨越中点）

3. 关键技巧：跨越中点时，在左半部分找最低买入价，在右半部分找最高卖出价

4. 复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)时间

5. 易错点：

   • 不能直接使用左右子问题的解作为跨越中点的解
   • 合并步骤的时间复杂度是O(n)，不是O(1)

💡 拓展思考

1. 如果允许多次买卖：这个问题会变成什么？可以用动态规划解决吗？

2. 如果允许往回开：问题会变得更简单还是更复杂？

3. 如果每个市场有交易成本：算法需要如何修改？

4. 与股票问题的区别：为什么股票问题可以转化为最大子数组问题，而这个问题不行？

📚 相关知识点

• 分治法：要点5-贪心法、分治法、动态规划
• 主方法：要点3-推导递推关系的渐进阶(主方法)
• 算法复杂度分析：要点2-比较不同函数的渐进阶大小

💡记忆口诀：分治买卖苹果，左右分别求解，跨越中点找最低买最高卖，三者取最优！