2018年3月31日 星期六

[Note #3][Algorithm] Kadane’s algorithm


Maximum subarray sum

Given an array of n numbers, our task is to calculate the maximum subarray sum, i.e., the largest possible sum of a sequence of consecutive values in the array.

1. Brute force: O(n^3) or O(n^2).

2. Divide and Conquer: O(n log(n)).

3. Kadane’s algorithm (Dynamic Programming): O(n)

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
    sum = max(array[k], sum + array[k]);
    best = max(best, sum);
}
cout << best << "\n";



[FWD] Book: Competitive Programming


First edition: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.457.3263&rep=rep1&type=pdf (The latest edition is the 3rd but not free in the Internet.)

Related book: Antti Laaksonen, Competitive Programmer’s Handbook. [PDF]


2018年3月9日 星期五

王玉皇《刑罰與社會規訓》


原本以為會講很多 Michel Foucault 理論的東西,不過這本書談幾個重要議題,相互印證 Michel Foucault 講的東西,突然覺得很有啟發性,畢竟理論還是要能夠結合現實發生的問題。以台灣來說問題大概就是:
  • 吸毒行為
  • 販賣毒品行為
  • 原住民犯罪

簡單引幾段話:

「社會大眾自己要求制定規範來管理自己、規訓自己,並要求國家行政體系大量進入原本應該屬於私人的生活領域。因此,任何足以使個人失去自我控制能力的行為,都有可能因為涉及到公眾福祉的損害,而成為公共討論的議題,或受到公共輿論的譴責與非難。」

「我國森林法雖規定,森林以國有為原則。然而,對於世居於山區的原住民而言,這樣的規定無異是強迫他們放棄原本對山林自然資源的依賴,也是一種限制原住民傳統生活與習慣的刑事法規範。雖然這樣的刑事法規範,有其保護森林資源的重要意義存在,但同時也是一種企圖強迫原住民改變既有生活型態的規範。」


再深入的問題,可能答案要往哲學方向找了,國家並不能幫你解決問題,我還是主張國家的本質就是邪惡。

2018年3月2日 星期五

薩米爾欽《我們》

之前翻過傅柯《規訓與懲罰》,這本《我們》頗有呼應之勢。


「世界上有兩個樂園,沒有自由的幸福,和沒有幸福的自由。」


先簡單說明一下傅柯「全景敞視監獄」概念。在一個圓形裡面,圓周位置是一間又一間的全透明的玻璃囚室,圓心之處有一座塔上面裝滿監視器,在邊緣的囚犯無法得知自己是否被監視,長期處於不安之中,只得保持秩序。

(老大哥正在看著你。)

(如果沒有違法就不必擔心監聽。)


不只是小說,比較貼近台灣生活的就是路上監視器及無所不在的監聽,我們早已踏上房子變透明的路上。這本小說由野人出版社出版,以下把有意思的片段寫在下面,供自己參考。


「坐在那堆可笑的髒兮兮葉子上的黃眼睛傢伙,牠的生活根本不可能用數字加以計算,可要是這種生活竟然比我的更快樂,那可怎麼辦!」(P109)


在國家面前,要說我有任何權利,這簡直就像在斷言一克在天平上可以與一噸抗衡!合乎情理的分配應該是這樣的:權利由噸享用,義務讓克承擔。想要從一無所有發展到偉大,最自然而然的辦法就是忘記一個人是一克,並牢記一個人只是一噸的百萬分之一!」(P131-132)


「他們知道順從是美德,驕傲是邪惡。我們源自上帝,我源自魔鬼。」(P143)


大家盼望多時的一致日慶祝活動於昨天舉行。曾無數次證明他的無上智慧不可動搖的無所不能者獲得一致通過,連續第四十八次全票當選。慶祝活動中出現了一點騷亂,騷亂份子都是幸福的敵人,所幸他們為數不多。這些人由於其行為,自然喪失了擔任聯眾國基石的資格。眾所周知,他們的選票全部作廢,因為如果不這麼處置,我們不就相當於把闖進音樂廳病人的一聲咳嗽聲也視為一場偉大交響樂的一部分了嗎?」(P165)

(這跟二二八事件有很強的既視感。當我們認同潑漆事件,此時便順從了某個規訓。反對來說,當我們反對潑漆事件,我們又順從了另個規訓。只要我們在某件事訂個規則,自然就會產生犯規者,或者說,正因為我們要處罰那邊看不順眼的人,所以我們訂下了規則。撇開國家不談,我們是否對人類有足夠的同情心?)

(別忘了,這跟勞基法通過也有很強的既視感,規訓技術不同罷了。)


安安從小被放在理想型態下長大,台大醫院、台北市的月子中心、各式各樣的育兒知識、童書,以及長輩無微不至的愛護,此時安安是沒有自由的幸福,長大希望他能成為那時代的薩米爾欽、那時代的傅柯、那時代的班雅明、那時代的阿岡本、那時代自己的安安。