CS170 Efficient Algorithms and Intractable Problems HW4

课程主页：

课程视频：

参考资料：

这次回顾HW4。

$s=0,res=-\infty$
for $i=0,\ldots, n - 1$:
- $s = s + a[i]$
- $res= \max(res, s)$
- if $s < 0$:
  - $s= 0$
return $res$

$s$表示当前的子列和，如果$s<0$，那么包含这段会使得子列和更小，所以要利用$s=0$舍弃这部分的和。

时间复杂度显然为$O(n)$。

正确，利用反证法。

如果结论不成立，任取一棵MST $T$，那么$T\cup \{e\}$包含环，删除环中除了$e$以外的边$e’$依然构成MST，注意到$w(e) <w(e’)$，所以权重和更小，这就产生了矛盾。

正确，根据构造MST的过程即可得证。

参考资料：

考虑下图：

    1   1
  A---B---C
  |  / \  |
1 | /4 5\ | 1
  |/  6  \|
  D-------E

$BDE$为环，$BD$是唯一的最小权重边，但是MST $DABCE$中显然不包含边$BD$。

参考资料：

正确，利用反证法证明：

如果存在一棵MST $T$，使得$s\to t$的路径上有权重$>r$的边$e$，那么考虑删除$e$后构成的划分（$s,t$在划分的两部分），那么由于$s\to$存在$ r$路径，所以存在割$e’ \le r$，那么$T\cup \{e’\} - \{e\}$是一棵权重更小的树，这就产生了矛盾。

添加顺序：

B: (A, B)
E: (B, E)
D: (B, D)
C: (B, C)
F: (C, F)

考虑如下例子：

(A, B) : 3
(B, C) : 2
(C, D) : 1
(A, D) : 4

图示：

	  3
  A ----- B
  |       |
4 |       |  2
  |       |
  D ----- C
  	  1

从$A$开始运行Dijkstra，那么A->D的路径为A->D，但是这条边不会出现在MST中。

不正确，反例依然使用之前的例子：

(A, B) : 3
(B, C) : 2
(C, D) : 1
(A, D) : 4

图示：

	  3
  A ----- B
  |       |
4 |       |  2
  |       |
  D ----- C
  	  1

显然MST为：

 3
A ----- B
        |
        |  2
        |
D ----- C
	  1

如果首先在$\{A,D\}, \{B, C\}$运行算法，那么必然会包括边$(A,D)$，这就产生了矛盾。