HDOJ 1003 最大子序列和

这道关于DP的经典题终于花时间弄明白了。一定要记录一下啊。题目链接。

思路

对这个题目，其实最重要的是思路。参考了此博客上面的思路，在这里对DP求解的思路做一些整理。

设数组$arr$的长度为$n$，下标从$0$到$n-1$，则最后一个元素表示为$arr[n-1]$。对连续和最大的子数组（后称"最大子数组"），最后一个元素$arr[n-1]$有如下三种情况：

• $arr[n-1]$单独构成最大子数组
• 最大子数组以$arr[n-1]$结尾
• 最大子数组跟$arr[n-1]$没关系，最大子数组在$arr[0-n-2]$范围内，转为考虑元素$arr[n-2]$

从上面我们可以看出，问题分解成了三个子问题，最大子数组就是这三个子问题的最大值，现假设：

1. 以$arr[n-1]$为结尾的最大子数组和为$End[n-1]$
2. 在$[0,n-1]$范围内的最大子数组和为$All[n-1]$

如果最大子数组跟最后一个元素无关，即最大和为$All[n-2]$（存在范围为$[0, n-2]$），则解 $All[n-1]$ 为下述三种情况的最大值，即

• $arr[n-1]$
• $End[n-1]$
• $All[n-2]$

从后向前考虑，初始化的情况分别为$arr[0]$，以$arr[0]$结尾，即$End[0] = arr[0]$，最大和范围在$[0,0]$之内，即$All[0]=arr[0]$。根据上面分析，$All[i]$ 的值应该取下述三种情况的最大值：

• $arr[i]$
• $End[i-1]+arr[i]$
• $All[i-1]$

伪代码表示为：

/* DP base version*/
#define max(a,b) ( a > b ? a : b)
 
int Maxsum_dp(int * arr, int size)
{
    int End[30] = {-INF};
    int All[30] = {-INF};
    End[0] = All[0] = arr[0];
 
    for(int i = 1; i < size; ++i)
    {
        End[i] = max(End[i-1]+arr[i],arr[i]);
        All[i] = max(End[i],All[i-1]);
    }
    return All[size-1];
}

仔细看上面DP方案的代码，End[i] = max{arr[i],End[i-1]+arr[i]}，如果$End[i-1]<0$，那么$End[i]=arr[i]$，什么意思？

$End[i]$表示以i元素为结尾的子数组和，如果某一位置使得它小于0了，那么就自当前的$arr[i]$从新开始，且$End[i]$最初是从$arr[0]$开始累加的。

所以这可以启示我们：我们只需从头遍历数组元素，并累加求和，如果和小于0了就自当前元素从新开始，否则就一直累加，取其中的最大值便求得解。

为什么当sum<0时可以舍弃序列并重新扫描呢？

证明如下：

设$i$表示子序列的起始下标，$j$ 表示子序列的终止下标。

当我们得到一个子序列，如果子序列的第一个数是非正数，那么可以舍去，即$i = i + 1$

当一个子序列的前$n$个元素和为非正数时，是否也可以舍去呢？答案是可以的。

假设 $k\in[i,j]$，$sum(a,b)=\sum_{i=a}^barr[i]$，得： $sum(i,j)<0$

$\because sum(i,k)>0$ 且 $sum(i,k)+sum(k,j)=sum(i,j)$ $\therefore sum(k,j)<sum(i,j)<0$

所以如果把 $k$ 到 $j$ 的序列附加到 $j$ 之后的序列上，只会使序列越来越小。所以 $i$ 到 $j$ 的序列都可以舍去。

代码

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        //sc = new Scanner(new FileInputStream("src\\oj\\hdoj\\Q1003.txt"));
        int N = sc.nextInt();

        for (int l = 0; l < N; l++) {
            int n = sc.nextInt();
            int max = -999999, sum = 0, ci = 0, i = 0, j = 0;

            for (int k = 0; k < n; k++) {
                int tmp = sc.nextInt();
                if (sum < 0){
                    sum = tmp;
                    ci = k;
                } else {
                    sum += tmp;
                }
                if (sum > max){
                    j = k;
                    i = ci;
                    max = sum;
                }
            }

            System.out.println("Case " + (l+1) + ":" );
            System.out.println(max + " " + (i + 1) + " " + (j + 1));

            if (l < N - 1) {
                System.out.println();
            }
        }
    }
}