最長子序列dp 最詳細解析 poj2479

Maximum sum

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 44476	Accepted: 13796

Description

Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:

Your task is to calculate d(A).

Input

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input. 

Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.

Output

Print exactly one line for each test case. The line should contain the integer d(A).

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5      

Sample Output

13

簡單的dp題。
首先是dp，就是把大的問題細化為可以立即解決的小問題。

這有點像數列：先确定n=1的情況，再确定n和n-1的關系，即可得出數列的通項公式。

提一句，樓主聯考的時候，數列是最後一個大題，坐标浙江= =。

比如該題的尋找最大子序列，當n為1的時候很容易判定，取這唯一的一個值就好了，然後考慮n和n-1的關系。      

我們用a[n]來記錄每個值，用dp[n]來記錄過程。      

如果我們想由n-1的情況推出n的情況，我們是不是要知道n-1時前面的最大子序列和？ 而且，這個 和 是需要包含a[n-1]這個值的，否則a[n]無法和前面的序列相連。

思考之後我們可以的出，如果前面包含a[n-1]的最大子序列和，即dp[n-1],大于零，則我們可以得出：dp[n]=dp[n-1]+a[n] ,否則，dp[n]=a[n], 大于零就加上，有點貪心的感jio。
也是以，dp[]中是存在負數的，因為我們要保證 dp[n-1] 至少要包含 a[n-1]，否則無法相連，而且最大子序列 長度不能為0.

但此時dp[] 是最終答案了嗎？
明顯不是，因為 “最大子序列” 不要求每個dp[n-1]中包含a[n-1]。
但也已經接近尾聲了。
我們可以知道，不管“最大子序列”在哪裡結束，反正在 dp[n]前面的n-1 項中肯定存在，是以要求到dp[n]的最長子序列，隻需從頭到尾周遊更新一遍:

for(int i=1;i<n;i++)
　　if( dp[i-1] > dp[i] )
　　　　dp[i]=dp[i-1]

用l（左）數組和r（右）數組記錄。

好了，這樣子左右分别來一遍後，我們分别得到了 l[]和r[] 兩個數組，其中 l[t] 代表 【1，t】（閉區間）内的最大子序列和，r[t]則代表【t，n】的。

而對于這題我們隻需從1到n周遊一遍間斷點相加 r[] 和 l[] 的值即可得到最大值。
for(int i=1;i<n;i++)
{
　　ans= max ( ans , l[i-1]+r[i])
}
得出答案answer。
有幾個注意點：
1 一個測試點n是最大值50000，是以需要開大一點的數組，我因為這個找了半天錯= =。
2 間斷點本身隻能取一次，被左或右取均可。
3 代碼可以自己嘗試一下，不貼了就。

希望看到的提個意見，評個論。
然後貼一個網站，poj提目推薦
https://www.cnblogs.com/rainydays/p/3671118.html

類似題目，poj2593