PAT 甲级 1007 Maximum Subsequence Sum (25 分)（Java）

• PAT 甲级 1007 Maximum Subsequence Sum (25 分)（Java）
• • 题目
  • 题意解读
  • 解题思路
  • 解法
  • • 解法一
    • 解法二

题目链接

这题是经典的动态规划题：最大连续子序列和，这题多出来的就是如何存储这个最大子序列和的起始点和终点；

这题可以首先写出最基础的最大连续子序列和，然后在此基础上思考如何通过一定的数据结构保存最大连续子序列和的起点和终点；

需要注意的是：

1. 这题使用Scanner输入会超时，所以需要使用StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)))进行输入；
2. 若整个数组全部是负数，输出的最大子序列和是0，且输出序列的首尾的数字；

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

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        int n = (int)sc.nval + 1;
        int[] d = new int[n];
        for(int i=1; i 0){
                dp[i] = dp[i-1] + d[i];
                num[i] = num[i-1];
            }else{
                dp[i] = d[i];
                num[i] = i;
            }
            if(dp[i] > max){
                max = dp[i];
                start = num[i];
                end = i;
            }
        }
        if(max < 0){
            System.out.println(0 + " " + d[1] + " " + d[n-1]);
        }else{
            System.out.println(max + " " + d[start] + " " + d[end]);
        }
    }
}

如果想看最大连续序列和，只要将上述代码的num数组全部去掉即可；

可以在解法一的基础上进行空间优化；

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

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        sc.nextToken();
        int n = (int)sc.nval + 1;
        int[] d = new int[n];
        for(int i=1; i max){
                max = temp;
                start = tempIndex;
                end = i;
            }
        }
        if(max < 0){
            System.out.println(0 + " " + d[1] + " " + d[n-1]);
        }else{
            System.out.println(max + " " + d[start] + " " + d[end]);
        }
    }
}