1302：股票买卖

【算法分析】
动态规划：线性动规
该题可以抽象为：在一个长为n的数字序列上，第i个数字为a[i]。找满足1≤i1≤j1≤i2≤j2≤n的两个数对(i1, j1), (i2, j2)，使得a[j1]-a[i1]+a[j2]-a[i2]最大。
还可以简单描述为：定义区间差值为区间两端点数值的差，求一个数字序列上两个不相交的区间差值加和的最大值。（区间长度大于等于1）

定义数组de，de[i]指以a[i]为结尾的所有区间中，区间差值的最大的区间的区间差值。自然de[i]为当前数字a[i]减去第1到第i数字中的最小值。记mn为a[1]~a[i]中的最小值，那么de[i] = a[i] - mn。
类似地，定义数组db，db[i]指以a[i]为起始的所有区间中，区间差值的最大的区间的区间差值。自然db[i]为第i到第n数字中的最大值减去a[i]，记mx为a[i]~a[n]中的最大值，那么db[i] = mx - a[i]
1. 状态定义
状态定义：
dpe[i]：第1到第i个数字构成的所有区间中，区间差值最大的区间的区间差值。
dpb[i]：第i到第n个数字构成的所有区间中，区间差值最大的区间的区间差值。

以第1数字到第i数字为结尾的所有区间中区间差值的最大值，即为第1到第i个数字构成的所有区间中区间差值的最大值，即dpe[i]为de[1]~de[i]中的最大值。
所以dpe[i]为de[1]~de[i-1]中的最大值dpe[i-1]与de[i]相比的较大值，即dpe[i] = max(dpe[i-1], de[i])。
以第i数字到第n数字为起始的所有区间中区间差值的最大值，即为第i到第n个数字构成的所有区间中区间差值的最大值，即dpb[i]为db[i]~db[n]中的最大值，所以dpb[i]为db[i+1]~db[n]中的最大值dpb[i+1]与db[i]相比的较大值，即dpb[i] = max(dpb[i+1], db[i])

例如：

数据：5 14 -2 4 9 3 17

dp[i]? ?0 9 0 6 11 5 19
dpe[i] 0 9 9 9 11 11 19
db[i]? ?12 3 19 13 8 14 0
dpe[i] 19 19 19 14 14 14 0

2. 状态转移方程
集合：第1到第n个数字构成的所有区间
分割集合：枚举分割点，分成第1到第i个数字构成的区间，与第i到第n个数字构成的区间i从1循环到n-1，取a[1]~a[i]中区间差值的最大值dpe[i]。以及a[i+1]~a[n]中区间差值的最大值dpb[i+1]。加和为ans = dpe[i]+dpb[i+1]。对于每个i求出的ans，求最大值，得到的结果就是整个序列中两个不相交的区间的区间差值加和的最大值，即为原问题中两次买卖得到的最大利润。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define INF 0x3f3f3f3f
int t, n, ans, a[N], de[N], db[N], dpe[N], dpb[N];
int main()
{
    int mn, mx;
    scanf("%d", &t);
    while(t--)
    {
        memset(dpe, 0, sizeof(dpe));
        memset(dpb, 0, sizeof(dpb));
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        mn = a[1];
        for(int i = 1; i <= n; ++i)
        {
            mn = min(mn, a[i]);
            de[i] = a[i] - mn;//以a[i]为结尾的所有区间中，区间差值的最大的区间的区间差值。
            dpe[i] = max(dpe[i-1], de[i]);//第1到第i个数字构成的所有区间中，区间差值最大的区间的区间差值。
        }
        mx = a[n];
        for(int i = n; i >= 1; --i)
        {
            mx = max(mx, a[i]);
            db[i] = mx - a[i];//以a[i]为起始的所有区间中，区间差值的最大的区间的区间差值。
            dpb[i] = max(dpb[i+1], db[i]);//第i到第n个数字构成的所有区间中，区间差值最大的区间的区间差值。
        }
        ans = -INF;//原序列中不相交的两个区间的区间差值加和的最大值 
        for(int i = 1; i < n; ++i)//枚举分割点
            ans = max(ans, dpe[i]+dpb[i+1]);
        printf("%d\n", ans);
    }
    return 0;
}