POJ_2479与POJ_2593 Maximum Sum-白红宇

POJ_2479与POJ_2593 Maximum Sum

阅读量：4876 次

发布时间：2019-06-11

本文共 3627 字，大约阅读时间需要 12 分钟。

题目链接：

POJ 2479：http://poj.org/problem?id=2479

POJ 2593：http://poj.org/problem?id=2593

分类：动态规划

算法：两道题目除了输入格式不同以外，其它算法一样，利用双向动态规划算法。

（1）最原始的计算方法

设有数组 $A=\left \{ a_1,a_2,\cdots,a_n \right \}$ 长度为 $n$ ，用一个 $n\times n$ 的矩阵 $D$ 进行和的存储，即

$D_{ij}=\sum _{k=i}^{j}a_{k}$

则计算 $D_{ij}$ 的时间复杂度为：

$n+(n-1)+(n-2)+\cdots+1=\frac{n^2+n}{2}$

接下来，需要求出不相交的两段和的最大值 $D_{max}$ 。

设 $T$ 为数组 $A$ 的分界，则第一段是 $1\cdots T$ ，第二段是 $T+1 \cdots n$ ， $T$ 的取值范围为 $1\leqslant T \leqslant n-1$ ，因此计算最大值的过程中，需要比较的次数为：

$\sum _{T=1}^{n-1} \frac{T(T+1)}{2} + \frac{(T+1+n)(n-T)}{2}=\frac{n^3-n}{2}$

因此计算步骤为

$\frac{n^2+n}{2}+\frac{n^3-n}{2}=\frac{n^3+n^2}{2}$

因此渐进时间复杂度为 $O(n^3)$ 。

（2）利用单向动态规划算法

如果原题中是求一段连续子序列的和，即

$\max_{1\leqslant s\leqslant t\leqslant n}\left \{ \sum_{i=s}^{t}a_{i} \right \}$

因此可以利用动态规划算法（最优子结构的证明可以找一本算法书看一下）：

设 $d(i)$ 表示为到第 $i$ 个元素为止的连续子序列的最大值和，其具有如下的最优子结构：

$d(1)=a(1)$

$d(i)=\max\left \{ d(i-1)+a(i),a(i)) \right \}, 1<i\leqslant n$

因此当求两段和时，首先通过分界标识 $T$ 将数组 $A$ 分为两部分， $T$ 的取值范围为 $1\leqslant T<n$ ，再根据上述的最优子结构公式计算出第二段的最大值，再求和，最终结果即为

$\max_{1\leqslant T<n}\left \{ d(T)+\max_{T+1\leqslant j\leqslant n}\left \{ d'(j) \right \} \right \}$

其中， $d'(j)$ 为从第 $T+1$ 项开始利用动态规划计算的最大值。上式实质上的比较次数为一个二重循环，即为

$(n-1)+(n-2)+\cdots+1=\frac{n^2-n}{2}$

因此渐进时间复杂度为 $O(n^2)$ 。

（3）利用双向动态规划算法

由于是求不相交的两段连续子序列和的最大值，因此造成上述第（2）种算法耗时的主要原因在于需要用遍历的方法逐个比较最大值，因此需要双重循环。为了解决上述问题，从左至右以及从右至左分别采用动态规划，并且对 $d(i)$ 函数进行改进，其保存的不是至第 $i$ 个元素的最大值，而是小于或等于第 $i$ 个元素的最大值，在如下的程序中，用MAX变量进行赋值。因此最终仅需要执行单层循环3次，因此渐进时间复杂度为 $O(n)$ 。

后续工作的思考：需要对最优子结构进行数学证明。

POJ 2479 C++ 源码

1 #include
     
       2  3 using namespace std; 4  5 int A[100001] = {
   0};       // 初始化数组 6 int d1[100001] = {
   0};        // 状态方程，用于保存当前最大值 7 int d2[100001] = {
   0}; 8  9 int solve(int n);10 11 int main()12 {13     int T,n;14     scanf("%d",&T);15     for (int j = 0; j < T; j++)16     {17         scanf("%d",&n);18         for (int i = 0; i < n; i++)19             scanf("%d",&A[i]);20         printf("%d\n",solve(n));21     }22     return 0;23 }24 25 26 int solve(int n)27 {28     // O(n)29     int current = A[0];30     d1[0] = A[0];31     int MAX = A[0];32     for (int i = 1; i < n; i++)33     {34         if (current+A[i] >= A[i]) current = current + A[i];35         else current = A[i];36         if (current <= MAX) d1[i] = MAX;37         else38         {39             MAX = current;40             d1[i] = MAX;41         }42     }43     // O(n)44     MAX = A[n-1];45     current = A[n-1];46     d2[n-1] = A[n-1];47     for (int i = n-2; i >= 0; i--)48     {49         if (current+A[i] >= A[i]) current = current + A[i];50         else current = A[i];51         if (current <= MAX) d2[i] = MAX;52         else53         {54             MAX = current;55             d2[i] = MAX;56         }57     }58     int result = d1[0] + d2[1];59 60     for (int i=1; i < n-1; i++)61     {62         if (d1[i] + d2[i+1] > result)63             result = d1[i] + d2[i+1];64     }65     return result;66 }

POJ 2593 C++ 源码

1 #include
     
       2 #include
      
        3  4 using namespace std; 5  6 int A[100001] = {
   0};       // 初始化数组 7 int d1[100001] = {
   0};        // 状态方程，用于保存当前最大值 8 int d2[100001] = {
   0}; 9 10 int solve(int n);11 12 int main()13 {14     int n;15     while (scanf("%d",&n) && n!=0)16     {17         for (int i = 0; i < n; i++)18             scanf("%d",&A[i]);19         printf("%d\n",solve(n));20     }21     return 0;22 }23 24 25 int solve(int n)26 {27     // O(n)28     int current = A[0];29     d1[0] = A[0];30     int MAX = A[0];31     for (int i = 1; i < n; i++)32     {33         if (current+A[i] >= A[i]) current = current + A[i];34         else current = A[i];35         if (current <= MAX) d1[i] = MAX;36         else37         {38             MAX = current;39             d1[i] = MAX;40         }41     }42     // O(n)43     MAX = A[n-1];44     current = A[n-1];45     d2[n-1] = A[n-1];46     for (int i = n-2; i >= 0; i--)47     {48         if (current+A[i] >= A[i]) current = current + A[i];49         else current = A[i];50         if (current <= MAX) d2[i] = MAX;51         else52         {53             MAX = current;54             d2[i] = MAX;55         }56     }57     int result = d1[0] + d2[1];58 59     for (int i=1; i < n-1; i++)60     {61         if (d1[i] + d2[i+1] > result)62             result = d1[i] + d2[i+1];63     }64     return result;65 }