PAT 甲级【1007 Maximum Subsequence Sum】

本题是考察动态规划与java的快速输入：

1. max[i]表示第i个结尾的最大的连续子串和。b
2. begin[i]表示第[begin[i],i]为最大和的开始位置

超时代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.valueOf(br.readLine());
        String[] words = br.readLine().split(" ");
        int[] num = new int[k];
        int negativecount = 0;
        for (int i = 0; i < k; i++) {
            num[i] = Integer.valueOf(words[i]);
            if( num[i] <0){
                negativecount++;
            }
        }
        if( negativecount == k){
            System.out.println(0 + " "+num[0] +" "+num[k-1]);
            br.close();
            return;
        }
        int[] begin = new int[k];
        int[] max = new int[k];
        begin[0] = 0;
        max[0] = num[0];
        int dpmax = 0;
        for (int i = 1; i < k; i++) {
            if (max[i - 1] >=0) {
                max[i] = max[i - 1] + num[i];
                begin[i] = begin[i - 1];
            } else {
                max[i] = num[i];
                begin[i] = i;
            }
            if(max[i] > max[dpmax]){
                dpmax = i;
            }
        }


        System.out.println(max[dpmax]+" "+num[begin[dpmax]]+" "+num[dpmax]);

        br.close();
    }
}

未超时：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int k = (int)in.nval;
        int[] num = new int[k];
        int negativecount = 0;
        for (int i = 0; i < k; i++) {
            in.nextToken();
            num[i] = (int)in.nval;
            if( num[i] <0){
                negativecount++;
            }
        }
        if( negativecount == k){
            System.out.println(0 + " "+num[0] +" "+num[k-1]);
            return;
        }
        int[] begin = new int[k];
        int[] max = new int[k];
        begin[0] = 0;
        max[0] = num[0];
        int dpmax = 0;
        for (int i = 1; i < k; i++) {
            if (max[i - 1] >=0) {
                max[i] = max[i - 1] + num[i];
                begin[i] = begin[i - 1];
            } else {
                max[i] = num[i];
                begin[i] = i;
            }
            if(max[i] > max[dpmax]){
                dpmax = i;
            }
        }


        System.out.println(max[dpmax]+" "+num[begin[dpmax]]+" "+num[dpmax]);
    }
}

动态规划原理

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

最优子结构

具有最优子结构也可能是适合用贪心的方法求解。

注意要确保我们考察了最优解中用到的所有子问题。

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
4. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。方法是反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

要保持子问题空间尽量简单，只在必要时扩展。

最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题；
2. 确定最优解使用哪些子问题时，需要考察多少种选择。

子问题图中每个定点对应一个子问题，而需要考察的选择对应关联至子问题顶点的边。

无后效性

已经求解的子问题，不会再受到后续决策的影响。

子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

基本思路

对于一个能用动态规划解决的问题，一般采用如下思路解决：

1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 按顺序求解每一个阶段的问题。

如果用图论的思想理解，我们建立一个 有向无环图，每个状态对应图上一个节点，决策对应节点间的连边。这样问题就转变为了一个在 DAG 上寻找最长（短）路的问题（参见：DAG 上的 DP）