PKU2479-Maximum sum

題目：http://poj.org/problem?id=2479
所謂的一段區間[i,j]，必須i<=j (至少一個元素)
問最大取兩段不相交區間和是多少？
需要注意的是，再怎麼差也要取一個最大的。
(全是負數的話就得選最大的兩個負數)

(2011.12.16補上解題報告，姊妹題PKU2593買一送一)



程式碼：http://codepad.org/hcgmieWG

因為兩段區間不相交
肯定有一個在左邊，一個在右邊
索性作兩次最大區間和DP，一次從左邊掃到右邊，另一次反之(即程式碼left和right)
假設區間[i,j]的最大子區間和是f(i,j)
最後只要取最大的f(1,i)+f(i+1,N)就是答案！

是一道學完基本的最大子區間和以後，非常適合的練習題