# 台大 107 軟體
###### tags: `NTU` `107` `軟體`
1. E
2. D
3. B
4. B
5. B
6. A
7. D
8. B
9. B
10. A
11. B
12. C
13. B
14. B
15. C
16. C

(V)
(a)
(1) 5,3,1,2,4
:::info
greedy: 5,3,4,1,2=7
optimal: 4,2,5,1,3=9
:::
(2)
Max[i][j] = $a_i$...$a_j$ 的局部最大
Min[i][j] = $a_i$...$a_j$ 的局部最小

Max[i][j] = max($a_i$ - min[i + 1][j], $a_j$ - min[i][j - 1])
Min[i][j] = min($a_i$ - max[i + 1][j], $a_j$ - max[i][j - 1])

Max[i][i] = Min[i][i] = $a_i$

Max:
5 2 7 5 9
X 3 2 4 4
X X 1 1 5
X X X 2 2
X X X X 4

Min:
5 -2 -1 -5 -1
X 3 -2 0 -2
X X 1 -1 -1
X X X 2 -2
X X X X 4

(b)
(1)
queue:
假設有兩個 in, out 兩個 stack
push_back: 將 element push 進 in
pop_front: 如果 out 為空，則將 in 的所有元素 pop 出來，再依序 push 進 out 裡。然後再 pop out

deque:
push_back: 將 element push 進 in
push_front: 將 element push 進 out
pop_front: 如果 out 為空，將 in 一半位於底部的元素 pop 出來，再依序 push 進 out 裡，然後再 pop out
pop_back: 如果 in 為空，將 out 一半位於底部的元素 pop 出來，再依序 push 進 in 裡，然後再 pop in

(2)
push: 2
pop: 1
因為 push 和 pop 都是常數時間，因此 n 個 push/pop 為 O(n)

:::info
push 的 2 包念了從 in 轉移至 out 的「費用」
:::

(3)
最差的情況下，會在兩邊來來回回的，時間複雜度為：
$n+\frac{n}{2}+\frac{n}{4}+...+1\in O(n^2)$

VI
被上一題搞到沒力氣寫了