1305：Maximum sum

【算法分析】
?动态规划：线性动规
要在整个序列中取两个不重合的子段，分别记为子段1与子段2，记子段2的起始位置为i 。
以i 为分界线，将整个序列分为两部分，分别为下标1 ～ i ? 1 与下标i ～ n。

• 子段1存在于下标1 ～ i ? 1范围内，子段1的和应该最大，即为所有满足j < i的j 中，以j 为结尾的最大子段和。
• 子段2以i 起始，子段2的和应该最大，所以子段2应该为以i 为起始的最大子段和。

基于上述思路，应该先分别求以i为结尾以及以i为起始的最大子段和
记a[i]为第i个元素

1. 求以i为结尾的最大子段和
状态定义：dp1[i]:以i为结尾的最大子段和
状态转移方程：
分割集合：以i为结尾的子段
子集1：以i-1为结尾的子段，添加第i元素，构成以i为结尾的子段。该子段的和为dp1[i]=dp1[i-1]+a[i]
子集2：第i元素自己构成子段，子段和为：dp1[i]=a[i]
以上两种情况取最大值

2. 求以i为起始的最大子段和
状态定义：dp2[i]:以i为起始的最大子段和
状态转移方程：
分割集合：以i为起始的子段
子集1：以i+1为起始的子段，添加第i元素，构成以i为起始的子段。该子段的和为dp2[i]=dp2[i+1]+a[i]
子集2：第i元素自己构成子段，子段和为：dp2[i]=a[i]
以上两种情况取最大值
注意，求该状态时，下标从大到小遍历

3 求互不重叠的两个最大子段和的最大加和
i 从2循环到n?
以i 为分界线，将整个序列分为两部分，分别为下标1 ～ i ? 1 与下标i ～ n 。
设mx表示：满足1 ≤ j < i 的以j 为结尾的最大子段和dp1[j]中的最大值。i 每次增大1后，第一段取到的新元素的下标为i ? 1。更新mx，写法为mx = max(mx, dp1[i-1])。
以i为起始的最大子段和为dp2[i]
mx + dp2[i]为以i 为子段2的起始位置时能取到的最大的互不重叠的两个子段的加和。
在循环中求这个表达式求最大值，即为结果。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define N 50005
#define INF 0x3f3f3f3f //0x3f3f3f3f表示无穷大或极大值
int dp1[N], dp2[N], a[N];//dp1[i]:以i为末尾的子段的最大和 dp2[i]:以i为起始的子段的最大和
int main()
{
    int t, n;
    cin >> t;
    while(t--)
    {
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2)); 
        cin >> n;
        for(int i = 1; i <= n; ++i)
            cin >> a[i];
        for(int i = 1; i <= n; ++i)
            dp1[i] = max(dp1[i-1]+a[i], a[i]);
        for(int i = n; i >= 1; --i)
            dp2[i] = max(dp2[i+1]+a[i], a[i]);
        int mx = -INF, ans = -INF;//mx:1~i-1中最大子段和 ans:结果 两个不重合的子段的最大和 
        for(int i = 2; i <= n; ++i)//求1~i-1中最大子段和 与 以i开始的最大子串和 的加和的最大值
        {
            mx = max(mx, dp1[i-1]);
            ans = max(ans, mx + dp2[i]);
        }
        cout << ans << endl;
    }
    return 0;
}